×

Regularizing irregular graphs. (English) Zbl 0789.05085

A connected graph is highly irregular if the neighbours of every vertex all have distinct degrees. It is known that for each positive integer \(k\) there exists a unique unicyclic highly irregular graph \(U_ k\) of girth \(4k\) and order \(6k\) and maximum degree 3. The author shows that for each \(k\) there is an embedding of \(U_ k\) as an induced subgraph of a cubic self-centered graph \(H\) having connectivity and edge-connectivity 3. Moreover, the graph \(H\) that is constructed is such that its diameter is 4 if \(k=2\) and \(k+1\) otherwise. It is known that there exists a unique highly irregular \(d\times d\) bipartite graph \(B_ d\) with maximum degree \(d\). The author shows that for each \(d \geq 2\), the highly irregular graph \(B_ d\) can be embedded as induced subgraph in a \(d\)-regular self- centered graph with diameter 2 and connectivity and edge-connectivity both equal to \(d\).

MSC:

05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alavi, Y.; Chartrand, G.; Chung, F. R.K.; Erdős, P.; Graham, R. L.; Oellermann, O. R., Highly irregular graphs, J. Graph Theory, 11, 235-249 (1987) · Zbl 0665.05043
[2] Alavi, Y.; Buckley, F.; Shamula, M.; Ruiz, S., Highly irregular \(m\)-chromatic graphs, Discrete Mathematics, 72, 3-13 (1988) · Zbl 0667.05052
[3] Boesch, F.; Tindell, R., Connectivity and symmetry in graphs, (Harary, F.; Maybee, J. S., Graphs and Applications (1985), Wiley: Wiley New York), 53-67 · Zbl 0559.05056
[4] Ray-Chaudhuri, D. K., Characterizations of line graphs, J. Combin. Theory, 3, 201-214 (1967) · Zbl 0149.41304
[5] Wong, P. K., Cages—A survey, J. Graph Theory, 6, 1-22 (1982) · Zbl 0488.05044
[6] Godsil, C. D.; McKay, B. D., Graphs with regular neighborhoods, Lecture Notes in Mathematics, 829, 127-140 (1980) · Zbl 0453.05052
[7] Buckley, F., Self-centered graphs with a given radius, Congressus Numerantium, 23, 211-215 (1979)
[8] Buckley, F., Self-centered graphs, Ann. N.Y. Acad. Sci., 576, 71-78 (1989) · Zbl 0792.05050
[9] Kennedy, J. W.; Quintas, L. V., Extremal \(f\)-trees and embedding spaces for molecular graphs, Discrete Appl. Math., 5, 191-209 (1983) · Zbl 0505.05027
[10] Erdős, P.; Kelly, P., The minimal regular graph containing a given graph, Amer. Math. Monthly, 70, 1074-1075 (1963)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.