Some characterizations of graphs by star complements

DOI10.1016/S0024-3795(99)00179-2MaRDI QIDQ1970508zbMATH OpenOpenAlexWikidataFDO

Authors P. Rowlinson, Dragoš Cvetković, Slobodan K. Simić

Publication date 8 October 2000

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0024-3795(99)00179-2

adjacency matrix eigenvalue generalized line graph root graph star complements

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

Let \(G= (V,E)\) be a simple graph with \(|V(G)|= n\) and with \((0,1)\)-adjacency matrix \(A\), and let \(\mu\) be an eigenvalue of \(G\) with multiplicity \(k\). Then a star complement for \(\mu\) in \(G\) is defined to be an induced subgraph \(H= G-X\) such that \(|X|= k\) and \(\mu\) is not an eigenvalue of \(G-X\). If \(v_1,\dots, v_n\) are the vertices of \(G\) and if \(a_1,\dots, a_n\) are nonnegative integers then the generalized line graph be denoted by \(L(G; a_1,\dots, a_n)= L(G; a)\). Its root graph is defined as the multigraph \(U\) obtained from \(G\) by adding \(a_i\) pendant double edges at vertex \(v_i\) for each \(i= 1,\dots, n\). That means \(L(G; a)= L(U)\) if we understand that in \(L(U)\) two vertices are adjacent iff the corresponding edges in \(U\) have exactly one vertex in common. In their investigation, the authors use the graphs \(R_t\), \(t\geq 4\), and \(Q_t\), \(t\geq 5\). \(R_t\) is obtained by adding \(t-3\) pendant edges to one vertext of a triangle, and \(Q_t\) is obtained from a triangle by adding \(t-4\) edges at one vertex and one pendant edge at another. In four sections, the authors characterize connected graphs \(G\) related to generalized line graphs or their complements by \(\overline{L(R_t)}\), \(L(R_t)\), \(\overline{L(Q_t)}\) and \(L(Q_t)\) in the role of star complements for eigenvalues \(1\), \(-2\), \(1\) and \(-2\), respectively. The results are summarized by eight theorems. For example the case \(H=\overline{L(R_t)}\) and \(\mu= 1\) (Theorem 1.1) shall be mentioned here: Be \(G\) a maximal graph with \(\overline{L(R_t)}\), \(t\geq 5\), as a star complement for the eigenvalue \(\mu= 1\). If \(t\neq 8\), \(12\), \(13\) then one of the following holds: (1) \(G= \overline{L(K_t)}\); (2) \(G=\overline{L(K_{2,t- 2})}\cup K_2\); (3) \(G= K_{1,t- 3}\cup 2K_2\). In the three other cases maximal graphs \(G\) are characterized by analogous theorems [Theorem 2.1 \((t\neq 8)\), Theorem 3.1 \((t\neq 8,12,13)\), Theorem 4.1 \((t\neq 8)\)] and the case \(t= 8\) is treated in separated manner (Theorems 1.2, 2.2, 3.2 and 4.2).

Recommendations

Cited in

(29)

This page was built for publication: Some characterizations of graphs by star complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1970508)