Irregularity strength of regular graphs
Summary: Let \(G\) be a simple graph with no isolated edges and at most one isolated vertex. For a positive integer \(w\), a \(w\)-weighting of \(G\) is a map \(f:E(G)\rightarrow \{1,2,\dots,w\}\). An irregularity strength of \(G, s(G)\), is the smallest \(w\) such that there is a \(w\)-weighting of \(G\) for which \(\sum_{e:u\in e}f(e)\neq\sum_{e:v\in e}f(e)\) for all pairs of different vertices \(u,v\in V(G)\). A conjecture by \textit{R.J. Faudree} and \textit{J. Lehel} [Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 247-256 (1988; Zbl 0697.05048)] says that there is a constant \(c\) such that \(s(G)\leq\frac{n}{d}+c\) for each \(d\)-regular graph \(G, d\geq 2\). We show that \(s(G)< 16\frac{n}{d}+6\). Consequently, we improve the results by \textit{A. Frieze}, \textit{R.J. Gould}, \textit{M. Karoński}, and \textit{F. Pfender} [J. Graph Theory 41, No.\,2, 120--137 (2002; Zbl 1016.05045)] (in some cases by a \(\log n\) factor) in this area, as well as the recent result by \textit{B. Cuckler} and \textit{F. Lazebnik} [J. Graph Theory 58, No.\,4, 299--313 (2008; Zbl 1188.05112)].
- Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
- scientific article; zbMATH DE number 4142086
- On graph irregularity strength
- Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
- Irregularity strength of regular graphs of large degree
- A new upper bound for the total vertex irregularity strength of graphs
- Irregularity strength of digraphs
- Irregularity strength of corona of two graphs
- Colourings of graphs by labellings
- Distant total irregularity strength of graphs via random vertex ordering
- Neighbor sum distinguishing total coloring of sparse IC-planar graphs
- Distant total sum distinguishing index of graphs
- A note on asymptotically optimal neighbour sum distinguishing colourings
- Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10
- Irregular labelings of circulant graphs
- Distant sum distinguishing index of graphs
- On edge H-irregularity strengths of some graphs
- Neighbor sum distinguishing total choosability of 1-planar graphs with maximum degree at least 24
- Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture
- Neighbor sum distinguishing total colorings of triangle free planar graphs
- Neighbor sum (set) distinguishing total choosability via the combinatorial Nullstellensatz
- Distant irregularity strength of graphs with bounded minimum degree
- Total vertex irregularity strength of 1-fault tolerant Hamiltonian graphs
- Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic
- Neighbor distinguishing total choice number of sparse graphs via the combinatorial nullstellensatz
- A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles
- scientific article; zbMATH DE number 4142086 (Why is no real title available?)
- Distant irregularity strength of graphs
- Neighbor sum distinguishing index of planar graphs
- Minimum-weight edge discriminators in hypergraphs
- Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz
- Modular irregularity strength of graphs
- Neighbor sum distinguishing total colorings of planar graphs
- The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles
- On weight choosabilities of graphs with bounded maximum average degree
- Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
- Distant sum distinguishing index of graphs with bounded minimum degree
- On vertex and edge \(H\)-irregularity strengths of graphs
- Irregular subgraphs
- Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz
- A generalization of Faudree–Lehel conjecture holds almost surely for random graphs
- On the asymptotic confirmation of the Faudree-Lehel conjecture for general graphs
- Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
- Short proof of the asymptotic confirmation of the Faudree-Lehel conjecture
- Sum-distinguishing number of sparse hypergraphs
- Bounding the distant irregularity strength of graphs via a non-uniformly biased random weight assignment
- Modular irregularity strength of dense graphs
- Modular irregularity strength of the corona product of graphs
- Maximum locally irregular induced subgraphs via minimum irregulators
- Irregularity strength of regular graphs of large degree
- The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel
- Finding irregular subgraphs via local adjustments
- Neighbor sum distinguishing total choosability of 1-planar graphs with maximum degree at least 15
- The 1-2-3 conjecture holds for graphs with large enough minimum degree
- On asymptotic confirmation of the Faudree-Lehel conjecture on the irregularity strength of graphs (extended abstract)
- An iterative approach to graph irregularity strength
- Parameterised distance to local irregularity
- On the neighbor sum distinguishing total coloring of planar graphs
This page was built for publication: Irregularity strength of regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010805)
