Also available at http://amc.imfm.si
ISSN 1855-3966 (printed ed.), ISSN 1855-3974 (electronic ed.)
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 126–136
Some Star Complements for the Second Largest
Eigenvalue of a Graph
Zoran Stanić ∗
Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11000 Belgrade, Serbia
Received 19 July 2007, accepted 11 September 2008, published online 14 October 2008
Abstract
The star complement technique is a spectral tool recently developed for constructing some
bigger graphs from their smaller parts, called star complements. Often the implementation of
this technique requires the use of computers. Therefore, we develop an SCL (star complement
library) – a set of programs providing quick implementation of those technique. Here, we
present the facilities of SCL. In further, we determine some star complements for 1 or
√
5−1
2
as the second largest eigenvalue of a graph. Finally, using the SCL, we consider the maximal
extensions of the star complements obtained.
Keywords: Adjacency matrix, graph eigenvalues, star complement, divisor concept, mathematical soft-
ware.
Math. Subj. Class.: 05C50, 68T35
1 Introduction
We consider only simple graphs, that is finite, undirected graphs without loops or multiple
edges. If G is such a graph with vertex set V (G) = {1, 2, . . . , n}, the adjacency matrix
of G is n × n matrix A = A(G) = (aij), where aij = 1 if there is an edge between the
vertices i and j, and 0 otherwise. The eigenvalues of G, denoted by λ1 ≥ λ2 ≥ · · · ≥ λn,
are just the eigenvalues of A. Additionally, for connected graphs λ1 > λ2 holds. The
characteristic polynomial of G is the characteristic polynomial of its adjacency matrix given
by PG(λ) = det(λI −A). For more details on graph spectra, see [3].
Our main goal is to introduce the facilities of freely available software SCL and to identify
some graphs having the simple structure which can be star complements for some specific
second largest eigenvalues. The graphs whose second largest eigenvalue is (less than or) equal
∗Research is partially supported by Serbian Ministry of Science, Project 144032D.
E-mail address: zstanic@matf.bg.ac.yu (Zoran Stanić)
Copyright c© 2008 DMFA – založništvo
Z. Stanić: Some Star Complements for the Second Largest Eigenvalue of a Graph 127
to 1 or
√
5−1
2 are intensively studied in the literature and they are not completely determined
so far. Therefore, the maximal extensions which are determined in this paper can be viewed
as a result from that context as well. Additionally, the maximal extensions obtained have
small number of distinct eigenvalues, and they can be interesting in some future research.
In Section 2, we give the main definitions, fix some notation and mention some results
from the literature in order to make the paper more self–contained. In Section 3, we describe
the software SCL which implements an algorithm (originally described in [10]) for construct-
ing the maximal graphs with a specified star complement for a specified eigenvalue. In the
remaining two sections, we consider some star complements for the second largest eigenvalue
of a graph. First, we complete earlier calculation from [14] which determine the unicyclic
star complements for 1 as the second largest eigenvalue. In further we determine all cocktail
party graphs and the graphs with up to five vertices which can be star complements for the
same eigenvalue. Finally, we determine all trees, unicyclic and bicyclic graphs which can be
star complements for
√
5−1
2 as the second largest eigenvalue. Using the SCL, we consider the
maximal extensions for all star complements obtained.
2 Preliminaries
First, we give a short description of the star complement technique. If µ is an eigenvalue ofG
of multiplicity k, then a star set for µ in G is a set X of k vertices taken from G such that µ is
not an eigenvalue ofG−X . The graphH = G−X is then called a star complement for µ inG
(or a µ–basic subgraph of G in [10]). Star sets and star complements exist for any eigenvalue
and any graph; they need not be unique. In addition, for any eigenvalue µ of a connected
graph G, G has a connected star complement for µ (see [10]). The H–neighborhood of an
arbitrary vertex in X contains all its neighbors from H . The H–neighborhoods of vertices in
X can be shown to be non–empty and distinct, provided that µ 6∈ {−1, 0} (see [6], Chapter
7). If t = |VH |, then |X| ≤
(
t
2
)
(see [1]) and this bound is best possible.
It can be proved that if Y is a proper subset of X then X −Y is a star set for µ in G−Y ,
and therefore H is a star complement for µ in G − Y . If G has star complement H for µ,
and G is not a proper induced subgraph of some other graph with star complement H for
µ, then G is a maximal graph with star complement H for µ, or it is an H–maximal graph
for µ. By the above remarks, there are only finitely many such maximal graphs, provided
µ 6∈ {−1, 0}. In general, there will be only several maximal graphs, possibly of different
orders, but sometimes there is a unique maximal graph (if so, this graph is characterized by
its star complement for µ).
We now mention some results from the literature regarding the star complement technique
(they are taken from [5], [6] and [7]).
The following result is known as the Reconstruction Theorem (see, for example, [6],
Theorems 7.4.1 and 7.4.4).
Theorem 1. Let G be a graph with adjacency matrix(
AX B
T
B C
)
,
where AX is the adjacency matrix of the subgraph induced by the vertex set X . Then X is a
star set for µ if and only if µ is not an eigenvalue of C and µI −AX = BT (µI − C)−1B.
128 Ars Mathematica Contemporanea 1 (2008) 126–136
From the above, we see that if µ,C and B are fixed then AX is uniquely determined. In
other words, given the eigenvalue µ, a star complement H for µ, and the H–neighborhoods
of the vertices in the star set X , the graph G is uniquely determined. In the light of these
facts, we may next ask to what extent G is determined only by H and µ. Having in mind the
observation above, it is sufficient to consider graphs G which are H–maximal for µ.
Following [2], [14] and [13], we will now fix some notation and terminology. Given
a graph H , a subset U of V (H) and a vertex u not in V (H), denote by H(U) the graph
obtained from H by joining u to all vertices of U . We will say that u (U , H(U)) is a good
vertex (resp. good set, good extension) for µ and H , if µ is an eigenvalue of H(U) but is
not an eigenvalue of H . By Theorem 1, a vertex u and a subset U are good if and only if
bTu (µI − C)−1bu = µ, where bu is the characteristic vector of U (with respect to V (H))
and C is the adjacency matrix of H . Assume now that U1 and U2 are not necessarily good
sets corresponding to vertices u1 and u2, respectively. LetH(U1, U2; 0) andH(U1, U2; 1) be
the graphs obtained by adding to H both vertices, u1 and u2, so that they are non–adjacent in
the former graph, while adjacent in the latter graph. We say that u1 and u2 are good partners
and that U1 and U2 are compatible sets if µ is an eigenvalue of multiplicity two either in
H(U1, U2; 0) or in H(U1, U2; 1). (Note, if µ 6∈ {−1, 0}, any good set is non–empty, any two
of them if corresponding to compatible sets are distinct; see [6], cf. Proposition 7.6.2.) By
Theorem 1, two vertices u1 and u2 are good partners (or two sets U1 and U2 are compatible)
if and only if bTu1(µI − C)
−1bu2 ∈ {−1, 0}, where bu1 and bu2 are defined as above. In
addition, it follows (again by Theorem 1) that any vertex setX in which all vertices are good,
both individually and in pairs, gives rise to a good extension, say G, in which X can be
viewed as a star set for µ, while H as the corresponding star complement.
The above considerations shows us how we can introduce a technique, also called a star
complement technique, for finding (or constructing) graphs with certain spectral properties.
In this context the graphs we are interested in should have some prescribed eigenvalue usually
of a very large multiplicity. If G is a graph in which µ is an eigenvalue of multiplicity k > 1,
then G is a good (k–vertex) extension of some of its star complements, say H (in particular,
G is H–maximal for µ). The star complement technique consists of the following: In order
to find H–maximal graphs for µ ( 6= −1, 0), we form an extendability graph whose vertices
are good vertices for µ and H , and add an edge between two good vertices whenever they
are good partners. Now it is easy to see that the search for maximal extensions is reduced
to the search for maximal cliques in the extendability graph (see, for example, [10], [5] or
[7]). Of course, among H–maximal graphs some of them can be mutually isomorphic. So,
we determine how many different isomorphism classes they belong to.
Now we give a description of a divisor concept. Given an s × s matrix D = (dij), let
the vertex set of a graph G (of order n) be partitioned into non–empty subsets V1, V2, . . . , Vs
so that for any i, j ∈ {1, 2, . . . , s} each vertex from Vi is adjacent to exactly dij vertices of
Vj . The multidigraph F with adjacency matrix D is called a front divisor of G, or briefly, a
divisor of G (see [6], Definition 2.4.4).
The eigenvalue λ of graph G is a main eigenvalue if and only if the corresponding eigen-
vector is not orthogonal to (1, 1, . . . , 1)T (compare [6], p. 25 and Theorem 2.2.3). Otherwise,
λ is said to be a non–main eigenvalue of G. The main part of the spectrum of G consists of
all its main eigenvalues.
It is known that the characteristic polynomial of a divisor divides the characteristic poly-
nomial of a graph (cf. [6], p. 38). Moreover, due to Theorem 2.4.5 of [6], we have that the
Z. Stanić: Some Star Complements for the Second Largest Eigenvalue of a Graph 129
1
23
4 n (≥ 4)
K
Figure 1: The infinite family of unicyclic star complements for 1 as the second largest eigen-
value (the vertices 4, . . . , n form a totaly disconnected graph).
spectrum of any divisor F of graph G includes the main part of the spectrum of G.
We conclude this section by the following two definitions. The cocktail party graph with
2k vertices, denoted by CPk, is a complement of kK2 (a regular graph of degree 1, with 2k
vertices). An arbitrary connected graph is said to be k–cyclic if m = n+ k+ 1 holds, where
n and m are its order and size, respectively. For k = 0, 1 and 2 we get trees, unicyclic and
bicyclic graphs, respectively.
3 SCL – star complement library
The SCL is free software which can be redistributed and/or modified under the terms of the
GNU General Public License as published by the Free Software Foundation version 2.
There are three versions (written in C++) of SCL: v. 1.0 was written by Zoran Stanić,
while most of the code of v. 2.0 and 2.1 was written by Zoran Stanić and Nedeljko Stefanović
(the only exception is the file cliques.cpp regarding the maximal clique search written by
Kevin O’Neill – this part of the software one can redistribute and/or modify under the terms
of the GNU General Public License as published by the Free Software Foundation; either
version 2 of the License, or any later version). The SCL 1.0 is written for author’s personal
use. Namely, most of computational results from [13] and [14] are obtained by using it. There
is just one difference between versions 2.0 and 2.1: v. 2.0 is a platform independent version
with no GUI (graphical user interface), while v. 2.1 includes a GUI (developed by using QT
OpenSource). SCL 2.0 and SCL 2.1 are available at www.matf.bg.ac.yu/∼zstanic/scl.htm
(the same link can be found at http://dmoz.org/Science/Math/Combinatorics/Software/ ).
The distribution of SCL 2.x includes an executable file, a complete source, Users Guide
(including a description of the star complement technique) and a number of examples.
4 Some star complements for 1 as the second largest eigenvalue
4.1 The unicyclic graphs
In [13] and [14] the authors use the star complement technique to obtain some of the graphs
whose second largest eigenvalue is equal to 1. In the later paper all unicyclic star comple-
ments for 1 as the second largest eigenvalue are determined. Namely, there are nine such
graphs plus one infinite family (see Figure 1). For each of nine finite graphs, the good ver-
tices and the maximal extensions are determined, while the infinite family is left for future
research. Here we complete this.
In the next theorem we identify all good sets for the infinite family of graphs depicted in
Figure 1.
130 Ars Mathematica Contemporanea 1 (2008) 126–136
Theorem 2. Let K be the graph from Figure 1, and let U be a subset of V (K). Further, let
Tn−5 denote a set of any n − 5 of the terminal vertices of K, while T denotes a set of all
terminal vertices of K. The graph K(U) is a good extension if and only if U has one of the
following forms:
1. {i} (4 ≤ i ≤ n);
2. {1, i} (4 ≤ i ≤ n);
3. {2, 3} ∪ Tn−5;
4. {2} ∪ T and {3} ∪ T , with n = 7;
5. {1, 2} ∪ T and {1, 3} ∪ T , with n = 11;
6. {2, 3}, with n = 5;
7. {1, 2, 3}, with n = 7;
8. {2} and {3}, with n = 7;
9. {1, 2} and {1, 3}, with n = 11.
Proof Let u, U and K(U) be good with respect to 1 as the second eigenvalue.
Assume firstly that u is adjacent to exactly k of the terminal vertices of K, and let l =
n − k − 3 (i.e. there are l of the terminal vertices non–adjacent to u). Denote by D the
matrix of divisor of K(U). Clearly, the vertices of K(U) can be partitioned into five sets:
V1 = {1}; V2 = {2, 3}; V3, containing k terminal vertices adjacent to u; V4, containing l
terminal vertices non–adjacent to u; V5 = {u}. Hence, D has the following form
D =

0 2 l k 0
1 1 0 0 0
1 0 0 0 1
1 0 0 0 0
0 0 0 k 0
 .
Note that K(U) contains two sets of duplicate vertices (they have the same open neigh-
bourhood): (1) the terminal vertices of K adjacent to u and (2) the terminal vertices of K
non–adjacent to u, as well as exactly two, so called, coduplicate vertices (they are labelled
by 2 and 3). Thus, K(U) contains 0 as an eigenvalue of multiplicity at least k + l − 2 and
−1 as an eigenvalue of multiplicity at least 1. In addition, all these eigenvalues belong to the
non–main part of K(U) spectrum (compare with [6]). Thus, the remaining five eigenvalues
of K(U) coincide with the eigenvalues of its divisor. Consequently, we have that 1 is an
eigenvalue of K(U) if and only if it is an eigenvalue of its divisor.
Clearly, 1 is an eigenvalue of D if and only if det(I −D) = 0 holds. We get
det(I −D) = −2 + 2k.
Hence, the good sets have the form {i} (4 ≤ i ≤ n).
Assume now that u is adjacent to the vertex labelled by 1 and to exactly k of the terminal
vertices of K. Using the notation and argument of the previous case we get
Z. Stanić: Some Star Complements for the Second Largest Eigenvalue of a Graph 131
D =

0 2 l k 1
1 1 0 0 0
1 0 0 0 1
1 0 0 0 0
1 0 0 k 0
 ,
and again
det(I −D) = −2 + 2k.
Hence, the good sets have the form {1, i} (4 ≤ i ≤ n).
Similarly, if u is adjacent to the vertices 2, 3 and to exactly k of the terminal vertices of
K, the good sets have the form {2, 3}∪Tn−5, where Tn−5 is specified above. If u is adjacent
to exactly one of the vertices 2, 3 and to exactly k of the terminal vertices of K, the good sets
exist only if n = 7, and then they have the form {2} ∪ T , and {3} ∪ T . The remaining cases
are similar and will be omitted.
Using the SCL, one can compute the maximal extensions for this family of star comple-
ments.
4.2 The cocktail party graphs
Here we consider the cocktail party graphs CPk as the star complements for 1 as the second
largest eigenvalue. We prove the following theorem.
Theorem 3. Let CPk be the cocktail party graph of order 2k, and let U be a subset of
V (CPk). The graph CPk(U) is a good extension if and only if U is:
1. a complement of any triangle of CPk or
2. any induced path of the length 2 of CP6.
Proof Let u, U and CPk(U) be good with respect to 1 as the second eigenvalue.
First we fix the neighborhood of u: let p pairs of non–adjacent vertices (in CPk) are
adjacent to u; there are q pairs of non–adjacent vertices such that u is adjacent to exactly one
vertex of each pair, and there are r pairs of non–adjacent vertices which are not adjacent to
u. Clearly, p + q + r = k. As in Theorem 2, the matrix D of the divisor CPk(U) has the
following form
D =

2p− 2 q q 2r 1
2p q − 1 q − 1 2r 1
2p q − 1 q − 1 2r 0
2p q q 2r − 2 0
2p q 0 0 0
 .
Since each eigenvalue of CPk(U) different from zero is an eigenvalue of its divisor, we
get that 1 is an eigenvalue of CPk(U) if and only if det(I −D) = 0 holds. We compute
det(I −D) = 3
(
9− 6 (2p+ 2q + r) + 4 (pq + pr + rq) + 3q2
)
.
132 Ars Mathematica Contemporanea 1 (2008) 126–136
First, if q is not odd then det(I −D) is odd. Further, if q ≥ 5, we get det(I −D) > 0.
Thus, det(I−D) 6= 0 holds, whenever q /∈ {1, 3}. If q = 1, we get det(I−D) = 2(−4p−r+
2pr) = 0. Only integral non–negative solution is (p, q, r) = (1, 1, 4) (for (p, q, r) = (0, 1, 0)
the graph considered reduces to K2 in which 1 is the largest eigenvalue), i.e. u is adjacent to
any induced path of the length 2 of CP6. For q = 3, we get det(I −D) = 2(3r+ 2pr) = 0.
The infinite family of solutions is (p, q, r) = (p, 3, 0), p ≥ 0, i.e. u is adjacent to the
complement of any triangle of CPk.
Let u(T ) and u(T ′) be good vertices adjacent to the complements of triangles T and T ′ of
CPk, respectively. Using the divisor concept we check that u(T ) and u(T ′) are good partners
in exactly two situations: (1) T and T ′ have two vertices in common while the remaining two
vertices are non–adjacent (here, u(T ) and u(T ′) are non–adjacent) and (2) T and T ′ have
one vertex in common while the remaining four vertices form a quadrangle (here, u(T ) and
u(T ′) are adjacent). Thus, the possible extensions of CPk, k ≥ 3, k 6= 6, can be obtained
by combining such good vertices. Much interesting case is CP6 since there we have another
type of good vertices (as it is proved in the previous theorem). This case is considered by
using the facilities of SCL, and the result is given in the next theorem.
Theorem 4. There are exactly nine non–isomorphic maximal extensions of star complement
CP6. Each has 26 vertices and contain the following good sets (the vertices of CP6 are la-
belled by 1, 2, . . . , 12, such that the vertices 2i−1 and 2i (i = 1, 2, . . . 6) are non–adjacent):
{1, 2, 3}, {1, 2, 4}, {3, 4, 5}, {3, 4, 6}, {1, 5, 6}, {2, 5, 6}. In the list below we give the spec-
trum, followed by the complements of the remaining good sets.
1. [−6.4999,−34,−2.0660,−24,−1.2435, 114, 15.8094] {8, 10, 12}, {7, 10, 12},
{8, 9, 12}, {7, 9, 12}, {2, 4, 6}, {1, 4, 6}, {2, 3, 6}, {1, 3, 6}
2. [−6.3716,−34,−2.2731,−24,−1.2510, 114, 15.8956] {8, 10, 12}, {7, 10, 12},
{8, 9, 12}, {7, 9, 12}, {1, 4, 6}, {2, 3, 6}, {1, 3, 5}, {1, 3, 6}
3. [−5.8856,−35,−24,−1.2626, 114, 16.1482] {8, 10, 12}, {7, 10, 12}, {8, 9, 12},
{7, 9, 12}, {2, 4, 6}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}
4. [−6.4172,−34,−2.0644,−24,−1.4107, 114, 15.8923] {8, 10, 12}, {7, 10, 12},
{8, 9, 12}, {7, 9, 12}, {1, 4, 6}, {2, 4, 6}, {1, 3, 6}, {2, 3, 6}
5. [−6.2877,−34,−2.2690,−24,−1.4213, 114, 15.9780] {8, 9, 12}, {7, 10, 12},
{7, 9, 12}, {7, 9, 11}, {1, 4, 6}, {2, 3, 6}, {1, 3, 5}, {1, 3, 6}
6. [−5.7930,−35,−24,−1.4360, 114, 16.2290] {8, 9, 12}, {7, 10, 12}, {7, 9, 12},
{7, 9, 11}, {2, 4, 6}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}
7. [−6.1355,−34,−26, 114, 16.1355] {8, 10, 12}, {7, 9, 12}, {7, 10, 11}, {8, 9, 11},
{1, 4, 6}, {2, 4, 6}, {2, 3, 6}, {1, 3, 6}
8. [−6,−34,−2.2195,−25, 114, 16.2195] {8, 10, 12}, {7, 9, 12}, {7, 10, 11},
{8, 9, 11}, {1, 4, 6}, {2, 3, 6}, {1, 3, 5}, {1, 3, 6}
9. [−5.4659,−35,−25, 114, 16.4659] {8, 10, 12}, {7, 9, 12}, {7, 10, 11}, {8, 9, 11},
{2, 4, 6}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}
4.3 Connected graphs with up to five vertices
Here we identify connected graphs with up to five vertices which can be star complements
for 1 as the second largest eigenvalue. Some similar results can be found in [4]. By using the
SCL, we get the result summarized in the following theorem.
Z. Stanić: Some Star Complements for the Second Largest Eigenvalue of a Graph 133
J3 J4
1
23
4
J1 J2
5 1
2
3
4
5
1
2
34
5 1
2
3
4
5
Figure 2: Connected star complements for 1 as the second largest eigenvalue with up to five
vertices.
Theorem 5. There are exactly 14 connected graphs up to five vertices which can be star
complements for 1 as the second largest eigenvalue. Those graphs are depicted in Figure 2.
As in the previous subsections, the maximal extensions can be easily computed. It is
interesting that each of the graphs J1 − J4 of Figure 2 has a unique maximal extension, i.e.
all its good vertices are mutually compatible. In addition, the maximal extensions of J2 and
J3 are isomorphic. In the list below, we present those extensions: the number of vertices, the
spectrum and the good sets are given.
J1: 9 [−24, 14, 4] {1, 4}, {1, 5}, {2, 4, 5}, {3, 4, 5}
J2: 7 [−2,−1.6458,−12, 12, 3.6458] {1, 2, 5}, {1, 4, 5}
J3: 7 [−2,−1.6458,−12, 12, 3.6458] {1, 2}, {1, 5}
J4: 6 [−2,−1.2361,−1, 0, 1, 3.2361] {1, 5}
5 Trees, unicyclic and bicyclic graphs as star complements for
√
5−1
2
as
the second largest eigenvalue
Let σ =
√
5−1
2 (the golden section). The graphs whose second largest eigenvalue does not
exceed the golden section are intensively studied in, for example, [8], [9], [12], e.g., or [11]
where a survey is given. Here we provide some results regarding the star complement tech-
nique.
Lemma 6. The path P3 is the only tree, while the graphs in Figure 3 are the only unicyclic
and bicyclic graphs which can be star complements for σ as the second largest eigenvalue.
Proof Since P4 contains σ as its second largest eigenvalue, an arbitrary tree which is a star
complement for σ as the second largest eigenvalue cannot contain P4 as an induced subgraph.
Thus, such a tree must be a star. Now, let Sn be a star of order n, and let u, U and Sn(U) be
good with respect to σ.
134 Ars Mathematica Contemporanea 1 (2008) 126–136
Assume first that u is adjacent to exactly k of the terminal vertices of Sn, and let l =
n − k − 1 (i.e. there are l terminal vertices not adjacent to u). Denote by D the matrix of
divisor of S(U). As in Theorems 2 and 3, we get
D =

0 l k 0
1 0 0 0
1 0 0 1
0 0 k 0
 ,
and
det(σI −D) = σ4 − (2k + l)σ2 + kl.
By putting σ4 = 2−3σ and σ2 = 1−σ into the equation above, we get that det(σI−D) = 0
holds only if k = l = 1.
Assume now that u is adjacent to the center of Sn and to exactly k of the terminal vertices
of Sn. We compute
D =

0 l k 1
1 0 0 0
1 0 0 1
1 0 k 0
 ,
and
det(σI −D) = σ4 − (2k + l + 1)σ2 − 2kσ + kl.
It can be easy checked that the equation det(σI −D) = 0 has no solutions in this case.
Therefore, a path P3 is the only tree which can be a star complement for σ as the second
largest eigenvalue.
Now, let us consider the unicyclic star complements. SinceCn (n ≥ 5) has second largest
eigenvalue greater than σ, we should consider only the graphs which contain cycle C3 or C4.
We find that C3, C4 and the graphs L1 − L3 of Figure 3 are the only unicyclic graphs whose
second largest eigenvalue does not exceed σ. In what remains we have to see which of these
graphs afford good extensions for σ. Firstly, for L1−L3 we can find at least one good set (in
addition, all good sets are given in the next theorem). Secondly, it is easy to check (say by a
brute force computation using SCL) that the cycles mentioned do not contain any good set.
Finally, considering the bicyclic graphs and their spectra we check that L4 − L6 are the
only solutions.
The results obtained by making use of SCL facilities are given in the next theorem.
Theorem 7. There are exactly nine non–isomorphic maximal extensions of star complements
L1 − L4 of Figure 3. In the list below the following data are given: the number of vertices,
the spectrum, followed by the good sets (the good sets of graphs 1 – 3 (resp. 4 – 6 and 7 –
9) regard star complement L1 (resp. L5 and L6) – the good sets correspond to the vertex
labelling).
1. 6 [−1.61802,−0.4142, 0.61802, 2.4142] {2}, {3}
Z. Stanić: Some Star Complements for the Second Largest Eigenvalue of a Graph 135
L2 L3 L4 L5 L6L1
1
23
4
1
2
3
4
5
1
2
3
4
5 6
Figure 3: The unicyclic and bicyclic star complements for
√
5−1
2 as the second largest eigen-
value.
2. 6 [−1.61802,−1.2360, 0.61802, 3.2360] {2}, {1, 2, 4}
3. 6 [−1.61802,−1.4995, 0.61802, 3.4495] {1, 2, 4}, {1, 3, 4}
4. 7 [−1.8434,−1.61802, 0.3068, 0.61802, 3.53663] {1, 2}, {1, 4}
5. 7 [−1.8284,−1.61802, 0, 0.61802, 3.8284] {1, 4}, {1, 3, 4, 5}
6. 8 [−1.8541,−1.61803, 0.61803, 4.8541] {3}, {1, 2, 3, 5}, {1, 3, 4, 5}
7. 8 [−2.1413,−1.61802, 0, 0.5151, 0.61802, 3.6262] {1, 2}, {1, 4}
8. 8 [−2,−1.61802,−1, 0.4384, 0.61802, 4.5616] {1, 2, 3, 6}, {1, 3, 4, 6}
9. 9 [−2.1240,−1.61803, 0.3985, 0.61803, 4.7255] {1, 4}, {1, 3, 4, 5}, {1, 3, 4, 6}
Remark 8. Note that L2 is the star complement of graphs 4 and 5, L3 is the star complement
of graphs 7 and 9, while L4 is the star complement of graphs 1–5 and 8.
References
[1] F. K. Bell and P. Rowlinson, On the multiplicities of graph eigenvalues, Bull. London Math. Soc.
35 (2003), 401–408.
[2] F. K. Bell and S. K. Simić, On graphs whose star complement for −2 is a path or a cycle, Linear
Algebra Appl. 347 (2004), 249–265.
[3] D. Cvetković, M. Doob and H. Sachs, Spectra of graphs – theory and application, 3rd edition,
Jonah Ambrosius Barth Verlag, Heidelberg–Leipzig, 1995.
[4] D. Cvetković, M. Lepović, P. Rowlinson and S. K. Simić, A database of star complements of
graphs, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 103–112.
[5] D. Cvetković and P. Rowlinson, Spectral graph theory, in: Lowell W. Beineke, Robin J. Wilson
(eds.), Topics in algebraic graph theory, Cambridge University Press, 2004, 88–112.
[6] D. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of graphs, Cambridge Univiversity Press,
Cambridge, 1997.
[7] D. Cvetković, P. Rowlinson and S. Simić, Spectral generalizations of line graphs – on line graphs
with least eigenvalue −2, Cambridge University Press, Cambridge, 2004.
[8] D. Cvetković and S. K. Simić, On graphs whose second largest eigenvalue does not exceed
√
5−1
2
,
Discrete Math. 138 (1995), 213–227.
[9] D. Cvetković and S. K. Simić, Minimal graphs whose second largest eigenvalue is not less than√
5−1
2
, Bull. Acad. Serbe. Sci. Math. 121 (2000), 47–70.
136 Ars Mathematica Contemporanea 1 (2008) 126–136
[10] M. Ellingham, Basic subgraphs and graph spectra, Australasian J. Comb. 8 (1993), 247–265.
[11] M. Petrović and Z. Radosavljević, Spectrally constrained graphs, Faculty of Science, Kragujevac,
Yugoslavia, 2001.
[12] S. K. Simić, Some notes on graphs whose second largest eigenvalue is less than
√
5−1
2
, Linear
and Multilin. Algebra 39 (1995), 59–71.
[13] Z. Stanić, On graphs whose second largest eigenvalue equals 1 – the star complement technique,
Linear Algebra Appl. 420 (2007), 700–710.
[14] Z. Stanić and S. K. Simić, On graphs with unicyclic star complement for 1 as the second largest
eigenvalue, in: Neda Bokan, Mirjana Djorić, Anatoly T. Fomenko, Zoran Rakić, Bernd Wegner,
Julius Wess (eds.), Proceedings of the Conference contemporary geometry and related topics,
Belgrade, June 26–July 2 2005, Faculty of Mathematics, Belgrade, 2006, 475–484.