Irregularity strength of dense graphs

DOI10.1016/0012-365X(91)90161-TMaRDI QIDQ5905417zbMATH OpenFDO

Authors Ralph Faudree, Michael Jacobson, Jeno Lehel, Lael F. Kinch

Publication date 26 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90161-T

zbMATH Keywords

complete graphsdense graphsirregular assignmentirregularity strength

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

Let \(G\) be a simple graph. Then positive integer weights can be assigned to the edges of \(G\) so that the weighted degrees of all vertices are distinct. An assignment of weights to the edges of \(G\) such that the weighted degrees of all vertices are distinct is called an irregular assignment of \(G\). The minimum of the largest weights over all irregular assignments of \(G\) is called the irregularity strength of \(G\). The authors determine the irregularity strength of certain unions of complete graphs. Moreover the irregularity strength of `dense' graphs is studied. In particular it is shown that if \(t\) is a fixed positive integer and if \(n\) is sufficiently large, then each graph of order \(n\) with minimum degree \(n-t\) has irregularity strength at most 3.

Recommendations

• Irregularity strength of dense graphs
• On graph irregularity strength
• On the irregularity strength of dense graphs
• A Tight Bound on the Irregularity Strength of Graphs

Cites work

• Conditions for sequences to be r-graphic
• scientific article; zbMATH DE number 4134084 (Why is no real title available?)
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 4142073 (Why is no real title available?)
• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Irregular networks, regular graphs and integer matrices with distinct row and column sums
• The irregularity strength of \(K_{m,m}\) is 4 for odd m

Cited in

(18)

• Irregularity strength of digraphs
• On the number of irregular assignments on a graph
• Distant total irregularity strength of graphs via random vertex ordering
• The irregularity strength of \(tK_ p\)
• The irregularity strength and cost of the union of cliques
• Total Edge Irregularity Strength of Complete Graphs and Complete Bipartite Graphs
• Distant irregularity strength of graphs
• scientific article; zbMATH DE number 15351 (Why is no real title available?)
• scientific article; zbMATH DE number 89403 (Why is no real title available?)
• On graph irregularity strength
• scientific article; zbMATH DE number 811600 (Why is no real title available?)
• On the irregularity strength of dense graphs
• Total vertex irregularity strength of dense graphs
• Irregularity strength of dense graphs
• Modular irregularity strength of dense graphs
• 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
• An iterative approach to graph irregularity strength

This page was built for publication: Irregularity strength of dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5905417)