𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On (1, 2)-realizable graphs

✍ Scribed by Peter Bugata; Mirko Horňák; Attila Nagy

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
711 KB
Volume
158
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph H is (1,2)-realizable if there exists a graph G in which each vertex has the first neighbourhood as well as the second neighbourhood isomorphic to H. We prove that if a ( I, 2)realizable graph H has n vertices, n > 3, then there is a unique connected graph G which realizes it and that G has 2n + 2 vertices. We give a necessary and sufficient condition for (1,2)-realizability of H, and use it to analyze regular (I, 2)-realizable graphs.

📜 SIMILAR VOLUMES

Sequences realizable by maximal k-degene
Sequences realizable by maximal k-degenerate graphs
✍ M. Borowiecki; J. Ivančo; P. Mihók; G. Semanišin 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB

A graph G is called k-degenerate if every subgraph of G has a vertex of degree at most k. A k-degenerate graph G is maximal k-degenerate if for every edge e E QG), G + e is not k-degenerate. Necessary and sufficient conditions for the sequence II = (d,, d2,. . . , d,) to be a degree sequence of a ma

Realizability of Graphs
Realizability of Graphs
✍ Maria Belk; Robert Connelly 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 173 KB
A note on distance matrices with unicycl
A note on distance matrices with unicyclic graph realizations
✍ J.M.S Simões-Pereira 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 643 KB

We give necessary and sufficient conditions for a distance matrix to have a unicycfic graph as unique optimal graph realization.