Originators: Ralph Faudree and Jenö Lehel; Mike Ferrara and Mike Jacobson (presented by Mike Ferrara - REGS 2008)
Definitions: A multigraph is irregular if no two vertex degrees are equal. A multigraph can be viewed as a weighted graph with nonnegative-integer weights on the edges. The degree of a vertex in a weighted graph is the sum of the incident weights. Chartrand et al. [CJLORS] defined the irregularity strength of a graph G, written s(G), to be the minimum of the maximum edge weight in an irregular multigraph with underlying graph G.
Background: Always s(G) is at least the number of vertices with degree 1. Amar and Togni [AT] proved that equality holds for trees without vertices of degree 2. Bohman and Kravitz [BK] proved that there are trees (with 2-valent vertices) whose irregularity strength is greater than c times the number of leaves, where c is some constant greater than 1.
Question 1: Prove or disprove that if a tree T has n1 leaves and n2 vertices of degree 2, then s(T)=n1+n2/2. If true, this would be sharp.
Lehel [L] presented a survey of results on s(G). A simple counting argument (see [CJLORS]) shows that s(G)≥⌊(n-1)/d⌋+1 when G is d-regular.
Conjecture 2 (Faudree-Lehel [FL]) There is a constant c such that if G is a d-regular graph with n vertices, then s(G)≤(n/d)+c.
Comments: Faudree and Lehel [FL] proved that s(G)≤⌈n/2⌉+9 when G is 2-regular. For general d, the best result is by Przybyło [P]: s(d)<16(n/d)+6. This improves results by Frieze-Gould-Karo\'nski-Pfender [FGKP] and Cuckler-Lazebnik [CL].
Question 3: What is the maximum irregularity strength of a graph with n vertices and m edges? Is it achieved by a regular or almost-regular graph?
Definitions: A (multi)digraph is irregular if its (in/out) degree pairs are distinct. The irregularity strength of a digraph D (same notation) is the minimum of the maximum multiplicity of an irregular multidigraph with underlying digraph D.
Comments: Ferrara-Gilbert-Jacobson-Whalen [FGJW] studied the irregularity strength of various classes of digraphs. They proved that the irregularity strength of the consistently directed path with n vertices is ⌈√(n-2)⌉ for n≥3, using a closed trail in a complete symmetric digraph with loops. For the antipath with n vertices, in which the edge directions alternate, they proved that the irregularity strength is ⌈n/4⌉, except one more when n≡ 3 mod 4.
Conjecture 4: The irregularity of any orientation of the path is between (1+o(1))√n and ⌈n/4⌉+1.
Question 5: For each graph G, what are the maximum and minimum of the irregularity strength among orientations of G? In particular, which graphs have irregular orientations (these are those where the least irregularity strength among orientations is 1)?
Comments: It is clear that if a graph G has an irregular orientation, then for all k the graph has at most k+1 vertices of degree k. Ferrara, Gilbert, and Jacobson (see [G]) obtained examples to show that this condition is not sufficient. They also proved that if G has at most one isolated vertex and at most two vertices with each positive degree, then G has an irregular orientation.
Conjecture 7 (Ferrara-Gilbert-Jacobson [G]): There exists a constant c less than 1 such that if G has at most c(k+1) vertices of degree k and δ(G) is sufficiently large, then G has an irregular orientation.
Conjecture 8 (Ferrara-Gilbert-Jacobson [G]): For every positive integer t, if G has at most min(t,k+1) vertices of degree k and δ(G) is sufficiently large, then G has an irregular orientation.
References:
[AT]
Amar, D.; Togni, O.; Irregularity strength of trees. Discrete Math. 190
(1998), no. 1-3, 15--38.
[BK] Bohman, Tom; Kravitz, David; On the irregularity strength of trees. J.
Graph Theory 45 (2004), no. 4, 241--254.
[CJLORS] Chartrand, Gary; Jacobson, Michael S.; Lehel, Jenö; Oellermann,
Ortrud R.; Ruiz, Sergio; Saba, Farrokh; Irregular networks. 250th Anniversary
Conference on Graph Theory (Fort Wayne, IN, 1986). Congr. Numer. 64 (1988),
197--210.
[CL] Cuckler, Bill; Lazebnik, Felix; Irregularity Strength of Dense Graphs.
J. Graph Theory (to appear).
[FL] Faudree, R. J.; Lehel, J.; Bound on the irregularity strength of regular
graphs. Combinatorics (Eger, 1987), 247--256, Colloq. Math. Soc. János
Bolyai, 52, North-Holland, Amsterdam, 1988.
[FGJW] Ferrara, M.; Gilbert, J.; Jacobson, M.; Whalen, T.; Irregularity Strength of Digraphs. Discrete Math (to appear).
[FGKP] Frieze, Alan; Gould, Ronald J.; Karo\'nski, Michał; Pfender, Florian;
On graph irregularity strength. J. Graph Theory 41 (2002), no. 2, 120--137.
[G] Gilbert, J.; Irregularity Strength of Digraphs, Ph.D. Dissertation, The University of Colorado Denver, May 2008.
[P] Przybyło, Jakub; Irregularity strength of regular graphs,
Electr. J. Combin. 15 (2008), Paper #82, 10 pages.