Some characterizations of graphs by star complements
type: Item
instance of: scholarly article
title: Some characterizations of graphs by star complements
zbMATH Open document ID: 0945.05042
DOI: 10.1016/S0024-3795(99)00179-2
author: P. Rowlinson
author: Dragoš Cvetković
author: Slobodan K. Simić
published in: Linear Algebra and its Applications
publication date: 2000-10-08T00:00:00Z
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\n…
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1420047
zbMATH Keywords: adjacency matrix
zbMATH Keywords: eigenvalue
zbMATH Keywords: generalized line graph
zbMATH Keywords: root graph
zbMATH Keywords: star complements
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s0024-3795(99)00179-2
OpenAlex ID: W2076234506
Wikidata QID: Q127109489
Recommended article: On the characterization of graphs by star complements
Recommended article: On graphs with prescribed star complements
Recommended article: Q4457010
Recommended article: Star complements and connectivity in finite graphs
Recommended article: Star complements and exceptional graphs
Recommended article: Star complements and edge-connectivity in finite graphs
Recommended article: Star complements in regular graphs: old and new results
Recommended article: On graphs with complete bipartite star complements
Recommended article: Q4901128
Recommended article: On star polynomials of complements of graphs
description: scientific article; zbMATH DE number 1420047