×

On graphs whose star complement for \(-2\) is a path or a cycle. (English) Zbl 1030.05072

Summary: It was proved recently by one of the authors that, if \(H\) is a path \(P_t\) (\(t>2\) with \(t\neq 7\) or 8) or an odd cycle \(C_t\) \((t > 3)\), then there is a unique maximal graph having \(H\) as a star complement for \(-2\). The methods employed were analytical in nature, making use of the reconstruction theorem for star complements. Here we offer an alternative approach, based on the forbidden subgraph technique. In addition, we resolve the exceptional situations arising when \(H=P_7\) or \(P_8\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C38 Paths and cycles

Software:

GRAPH
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bell, F. K., Characterizing line graphs by star complements, Linear Algebra Appl., 296, 15-25 (1999) · Zbl 0929.05072
[2] Bell, F. K., Line graphs of bipartite graphs with Hamiltonian paths, J. Graph Theory, 43, 137-149 (2003) · Zbl 1015.05044
[3] Bell, F. K.; Rowlinson, P., On the multiplicities of graph eigenvalues, Bull. London Math. Soc., 35, 401-408 (2003) · Zbl 1023.05097
[4] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg · Zbl 0824.05046
[5] Cvetković, D.; Doob, M.; Gutman, I.; Torgašev, A., Recent Results in the Theory of Graph Spectra (1988), North-Holland: North-Holland Amsterdam · Zbl 0634.05054
[6] Cvetković, D.; Doob, M.; Simić, S., Generalized line graphs, J. Graph Theory, 5, 385-399 (1981) · Zbl 0475.05061
[7] D. Cvetković, M. Lepović, P. Rowlinson, S.K. Simić, Computer investigations of the maximal exceptional graphs, Technical Report csm-160, Department of Computing Science and Mathematics, University of Stirling, 2001; D. Cvetković, M. Lepović, P. Rowlinson, S.K. Simić, Computer investigations of the maximal exceptional graphs, Technical Report csm-160, Department of Computing Science and Mathematics, University of Stirling, 2001
[8] Cvetković, D.; Lepović, M.; Rowlinson, P.; Simić, S. K., The maximal exceptional graphs, J. Combin. Theory Ser. B, 86, 347-363 (2002) · Zbl 1028.05063
[9] Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge University Press · Zbl 0878.05057
[10] Cvetković, D.; Rowlinson, P.; Simić, S. K., Graphs with least eigenvalue −2: the star complement technique, J. Algebraic Combin., 14, 5-16 (2001) · Zbl 0982.05065
[11] D. Cvetković, P. Rowlinson, S. Simić, Spectral generalizations of line graphs; a research monograph on graphs with least eigenvalue −2, Cambridge University Press, in press; D. Cvetković, P. Rowlinson, S. Simić, Spectral generalizations of line graphs; a research monograph on graphs with least eigenvalue −2, Cambridge University Press, in press
[12] Cvetković, D.; Simić, S., Graph theoretical results obtained by the support of the expert system “GRAPH”, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Nat. Sci. Math., 107, 19, 19-41 (1994)
[13] Ellingham, M. N., Basic subgraphs and graph spectra, Australas. J. Combin., 8, 247-265 (1993) · Zbl 0790.05057
[14] Rowlinson, P., On graphs with multiple eigenvalues, Linear Algebra Appl., 283, 75-85 (1998) · Zbl 0931.05055
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.