✦ LIBER ✦

The Irregularity Cost of a Graph

✍ Scribed by F. Harary; O.R. Oellermann

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 627 KB
Volume: 34
Category: Article
ISSN: 0898-1221
DOI: 10.1016/s0898-1221(97)00219-8

No coin nor oath required. For personal study only.

✦ Synopsis

A Multigraph His irregular if no two of its nodeahavethe samedegree.It hasbeen shownthat a graphis the underlying graphof some irregularMultigraph if and only if it has at most one trivialcomponentand no componentsof order2. We definethe irregularity cost of such a graph G to be the minimumnumberof additional edgeein an irregularMultigraph having G ss its underlying graph. We determinethe irregularity cost of certainregulargraphs,includingthose with a Hamiltonian path. We alsodetermine the irregularity cost of pathsandwheels,es examples of nearlyregulargraphs.At the oppositeextreme, wedetermine the irregularity cost of graphawith exactlyone pairof nodeeof equaldegree.As expected,theirccst is relatively low.

📜 SIMILAR VOLUMES

The irregularity cost or sum of a graph

✍ Frank Harary; Michael S. Jacobson; Ewa Kubicka; Grzegorz Kubicki; Ortrud R. Oell 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 169 KB

Working simultaneously in two teams [1,2], we have independently discovered essentially the same concept and many common results. As expected, each team used its own notation and terminology but the results are easily transformed between the two systems. We plan to publish our full papers separately

How local irregularity gets global in a

How local irregularity gets global in a graph

✍ Dieter Rautenbach; Lutz Volkmann 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB

## Abstract We prove asymptotically tight bounds on the difference between the maximum degree and the minimum degree of a simple graph in terms of its order and of the maximum difference between the degrees of adjacent vertices. Examples showing tightness and a conjecture are presented. © 2002 Wile

A note on the irregularity of graphs

✍ F.K. Bell 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 517 KB

The irregularity strength and cost of th

The irregularity strength and cost of the union of cliques

✍ Stanislav Jendroľ; Michal Tkáč; Zsolt Tuza 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 333 KB

Assign positive integer weights to the edges of a simple graph with no component isomorphic to Ki or 1£2, in such a way that the graph becomes irregular, i.e., the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregular assignments on

The spectral radius of irregular graphs

✍ Lingsheng Shi 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 135 KB

Let λ 1 be the largest eigenvalue and λ n the least eigenvalue of the adjacency matrix of a connected graph G of order n. We prove that if G is irregular with diameter D, maximum degree Δ, minimum degree δ and average degree d, then . The inequality improves previous bounds of various authors and

Embedding of graphs in two-irregular gra

Embedding of graphs in two-irregular graphs

✍ M. Axenovich; Z. Füredi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 1 views