Repetition number (2007)

Originator(s): Yair Caro (presented by D. West - REGS 2007)

Definitions: Let rep(G) denote the maximum multiplicity of an element in the degree list of G.

Background/motivation: It is an elementary exercise that every graph has a repeated vertex degree. To explore this phenomenon in more detail, Caro introduced the repetition number. The repetition number of a regular n-vertex graph is n. Thus the problem of interest is to find the smallest value of the repetition number in various classes, and indeed this question is related to some others (see [B,BS]).

A general lower bound [CW] from counting vertex degrees is that rep(G)≥n/(2d-2s+1), where n is the number of vertices, d is the average degree, and s is the minimum degree. Achieving equality in the lower bound requires a degree list with n/t copies of each vertex degree from s through 2d-s, where t=2d-2s+1. Caro and West [CW] proved that this bound is sharp by various explicit families in special cases and also by a general argument showing that a "packed list" sum is graphic if it satisfies obvious necessary conditions, where a list of ar+b integers from s to s+a is packed if it consists of r copies of each value from s to s+a-1 and b copies of s+a (here 1≤b≤r). The necessary and sufficient conditions are that the sum is even and ar+b>s+a.

The basic lower bound is asymptotically sharp for n-vertex graphs in various classes. The leading-order terms are

n/3 for trees,
n/5 for maximal outerplanar graphs,
n/7 for triangulations,
n/5 for triangulations with minimum degree 4, and
n/3 for triangulations with minimum degree 5.

For claw-free graphs, the repetition number may be as small as 2 when n is large. However, for line graphs the repetition number grows with n.

Conjecture 1: Every n-vertex line graph has repetition number at least cn^1/2, for some constant c.

Comments: The conjecture holds for line graphs of trees, but the best lower bound known for line graphs in general is cn^1/3 [CW]. For line graphs of trees with perfect matchings, maximal outerplanar graphs, and triangulations having 2-factors, the repetition number is linear in n.

Question 2: What are the expected value and concentration properties of the repetition number of the random graph?

Comments: The maximum and minimum degrees in the random graph differ from n/2 by about (1/2)√(nlogn). The pigeonhole principle thus implies that the repetition number is at least about 2√(n/logn). However, no good upper bound has been shown. A good understanding of the shape of the degree list of a random graph should resolve this question. More generally, it would be interesting to understand how the repetition number depends on p for the random graph with edge-probability p.

References:
[B] B. Bollobás, Degree multiplicities and independent sets in K₄-free graphs, Discrete Math. 158 (1996), 27--35.
[BS] B. Bollobás and A. D. Scott, Independent sets and repeated degrees, Discrete Math. 170 (1997), 41--49.
[CW] Yair Caro and Douglas B. West, Repetition number of graphs, submitted.