×
Šoltés, Ĺubomír

Neighbourhoods in line graphs. (English) Zbl 0766.05071

Math. Slovaca 42, No. 4, 427-436 (1992).
L. W. Beineke’s characterization [J. Comb. Theory 9, 129-135 (1970; Zbl 0202.557)] of line graphs by 9 forbidden induced subgraphs is now very well known. Since four of these obstructions have a vertex adjacent to all other vertices, forbidding these subgraphs means just a restriction on all the neighborhoods of the graph. Such graphs obeying these neighborhood conditions are called locally-\(\Theta\) graphs; they can be expressed in a very neat form, as is shown in the paper. Furthermore, for a graph \(H\), a locally-\(H\) graph is one where all neighborhoods are isomorphic to \(H\). It is shown that the question whether a locally-\(H\) graph is a line graph or not only depends on \(H\).
Reviewer: E.Prisner (Hamburg)

Cited in 1 Document

MSC:

05C75 Structural characterization of families of graphs

Keywords:

locally-\(H\) graph; neighborhoods; line graph

Citations:

Zbl 0202.557
PDF BibTeX XML Cite
\textit{Ĺ. Šoltés}, Math. Slovaca 42, No. 4, 427--436 (1992; Zbl 0766.05071)
Full Text: EuDML
  • logo of hbz
  • logo of WorldCat

References:

[1] BAUER D.: Line-graphical degree sequences. J. Graph Theory 4 (1980), 219-232. · Zbl 0403.05062
[2] BEHZAD M., CHARTRAND G., LESNIAK-FOSTER L.: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston, 1979. · Zbl 0403.05027
[3] BEINEKE L. W.: Derived Graphs and Digraphs. Beiträge zur Graphentheorie. Teubner, Leipzig, 1968, pp. 17-33.
[4] BEINEKE L. W., WILSON R. J.: Selected Topics in Graph Theory. Academic Press, London,1978. · Zbl 0423.00003
[5] BROUWER A. E., COHEN A. M, NEUMAIER A.: Distance-Regular Graphs. Springer-Verlag, Berlin, 1989. · Zbl 0747.05073
[6] DOYEN J., HUBAUT X., REYNAERT M.: Finite graphs with isomorphic neighborhoods. Colloquies de C.N.R.S.: Problèmes combinatoires et theòrie des graphes 111, CNRS, Paris, 1978. · Zbl 0413.05051
[7] HELL P.: Graphs with given neighborhoods I. Colloquies de C.N.R.S.: Problèmes combinatoires et thèorie des graphes, CNRS, Paris, 1978, pp. 219-223. · Zbl 0413.05052
[8] KRAUSZ J.: Dèmonstration nouvelle d’une thèorème de Whitney sur les rèseaux. (Hungarian), Mat. Fiz. Lapok. 50 (1943), 75-89. · Zbl 0061.41401
[9] SEDLÁČEK J.: Local properties of graphs. (Czech), Časopis Pěst. Mat. 106 (1981), 290-298. · Zbl 0478.05080
[10] ŠOLTÉS L.: Forbidden induced subgraphs for line graphs. · Zbl 0805.05072
[11] VANROOIJ A., WILF H. S.: The interchange graphs of a finite graph. Acta Math. Hungar. 16 (1965), 263-269. · Zbl 0139.17203
[12] ZELINKA B.: Polytopic locally linear graphs. Math. Slovaca 38 (1988), 99-103. · Zbl 0642.05029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.