PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 79(93) (2006), 1–12 DOI: 10.2298/PIM0693001M

MORE ABOUT SINGULAR LINE GRAPHS OF TREES

M. C. Marino, I. Sciriha, S. K. Simić, and D. V. Tošić

Communicated by Žarko Mijajlović

Abstract. We study those trees whose line graphs are singular. Besides new proofs of some old results, we offer many new results including the computer search which covers the trees with at most twenty vertices.

1. Introduction

Line graphs, and more generally, generalized line graphs, represent the class of graphs with several remarkable spectral properties. Recall first that their least eigenvalue is greater than or equal to −2 (see, for example, [3] for more details). Next, it is worth mentioning that 0 (or −1), can be, in many instances, the eigenvalue of these graphs. One reason for these phenomena is the presence of the so called duplicate (or co-duplicate) vertices. (Recall, following [4], that two vertices with the same open (closed) neighbourhood are called duplicate (resp. co-duplicate) vertices.) It is also noteworthy that the numbers 0 and −1 (as the eigenvalues of graphs) have a special role in spectral graph theory (see, for example, [2, Chapter 7]). In addition, graphs having 0 as an eigenvalue, i.e., singular graphs, are significant in mathematical chemistry (see, for example, [1]).

Given a simple graph H, its line graph (denoted by L(H)) is a graph G whose vertex set is equal to the edge set of H, with two vertices in G being adjacent if the corresponding edges in H are adjacent (i.e., have a common vertex). If G = L(H), then H is called a root graph of G.

A generalized line graph can be viewed as the line graph of some special type of multigraphs. A double hanging edge (at some vertex) is called a petal. A (simple) graph with petals attached at its vertices is, in fact, a root graph of a generalized line graph (denoted by Ĥ). We now emphasize only that two edges in the root graph are adjacent if they have exactly one common vertex (so that edges from the same petal are non-adjacent). We denote by L(Ĥ) the generalized line graph of Ĥ.

2000 Mathematics Subject Classification: Primary 05C50.

Key words and phrases: trees, line graphs, generalized line graphs, singular graphs.

The second author was supported by the University of Malta and the Italian Cultural Center in Malta. The third and fourth authors were supported by the Serbian Ministry of Science.

Example 1.1. In Fig. 1 we show the construction of a generalized line graph from its root multigraph. (Note that only two vertices of the root graph have petals).

a b  c  d ef  gi  jh L(Ĥ)^{ba  c  d ij  gh f  e Ĥ}

Figure 1. Construction of a generalized line graph from its root multi-graph.

We will consider generalized line graphs in Section 4.

For line graphs of trees, duplicate vertices can appear only if such a tree is equal to P_{4}. (More generally, if a connected graph is a line graph, then it can have duplicate vertices only if its root graph has P_{4} as its spanning subgraph.) Therefore, there remains to consider line graphs of trees, which have 0 as an eigenvalue, i.e., which are singular.

Singular line graphs of trees were already studied in literature. I. Gutman and I. Sciriha (see [5]) were the first who proved that singular line graphs of trees have 0 as a simple eigenvalue, i.e., of multiplicity (or nullity) one. Other proofs of this theorem, and related results, are provided by I. Sciriha (see [7, 8]). Here, we will offer yet another proof of this interesting theorem and, in addition, some other results.

For any graph, say G, let A(G) be its adjacency matrix, while B(G) its (vertex to edge) incidence matrix. Consider now the graph H, in the role of the root graph of G (so that L(H) = G). Then

B(H)B(H)^{T} = A(H) + D(H), B(H)^{T} B(H) = A(G) + 2I.

Here, D(H) is a diagonal matrix with (vertex) degrees along the diagonal.

The eigenvalues of a graph G are the eigenvalues of its adjacency matrix and are said to form the spectrum of G. So G is singular if its adjacency matrix is singular, or equivalently, if 0 is an eigenvalue of G. H is an L-singular graph (or, an LS graph for short) if L(H) is singular.

A λ-eigenvector of a (labelled) graph G is an eigenvector of G corresponding to the eigenvalue equal to λ; the λ-eigenspace of G is the corresponding eigenspace. A 0-eigenvector will be also called a kernel eigenvector.

If S is a finite set with |S| = s, then the s-dimensional vector space over ℝ will be denoted by ℝ^{S}. The elements in ℝ^{S} can be interpreted either as vectors (column matrices), or as functions from S to ℝ. We will make use of this fact interchangeably. To any (labelled) graph G = (V (G), E(G)) we associate the following two vector spaces:

ℝ^{V (G)} = {x | x : V (G) → ℝ} (vertex space);
ℝ^{E(G)} = {x̂ | x̂ : E(G) → ℝ} (edge space).

Given a vector x ∈ ℝ^{V (G)} (x̂ ∈ ℝ^{E(G)}) then x(v) (x̂(e)) is interpreted as the weight of a vertex v (edge e) of G with respect to x (resp. x̂).

Assume now that G = L(H). In the sequel, let E_{0}(G) ⊆ ℝ^{V (G)} be the 0eigenspace, or the null-space, of G. So E_{0}(G) = {x | A(G)x = 0}. In view of how line graphs are defined, we can now consider the vector space Ê(H) ⊆ ℝ^{E(H)}, in which x̂ ∈ Ê(H) if and only if x ∈ E_{0}(G), where x̂(e) = x(v) for any edge e of H and the corresponding vertex v of G. Clearly, E_{0}(G) ≅ Ê(H).

Let x be a λ-eigenvector of G (= L(H)), and x̂ the vector related to x as above. Then we have

λx(u) = ∑_{v∼u} x(v) u ∈ V (G),

where the summation is taken over all vertices v adjacent to u in G. Equivalently,

λx̂(e) = ∑_{f∼e} x̂(f) e ∈ E(H),

where the summing is taken over all edges f adjacent to e in H. In addition, (u, e) (and (v, f)) are the pairs of vertices and edges (from G and H, respectively) which correspond to one another when the line graph is being constructed. In particular, if G is singular then

∑_{v∼u} x(v) = 0 u ∈ V (G),

or equivalently, if H is an LS graph then

∑_{f∼e} x̂(f) = 0 e ∈ E(H).

Furthermore, since vector spaces E_{0}(G) and Ê(H) are isomorphic we will sometimes drop the symbol ˆ (and the names of the graphs) from our notation. The basic terminology follows [6] (for graph spectra, the reader is referred to [1]).

The plan of the paper is as follows: in Section 2, we give some basic results including new (and shorter) proofs of some basic theorems; in Section 3, we discuss some ways of constructing LS trees, or of reducing them to simpler ones; in Section 4, we give some results obtained by a computer search; finally, in Section 5, we add some further considerations related to the topic in question.

2. Basic results

Let G = L(H), where H is not necessarily a tree. We will now introduce yet another vector space (a subspace of ℝ^{V (H)}), denoted by E^{+}(H), and defined as follows:

E^{+}(H) = {y | y = B(H)x, x ∈ Ê(H)}.

Note, y(u) = ∑_{e∼u} x(e), where e ∼ u here means that an edge e is incident to the fixed vertex u (of H). We will now prove the following result.

Lemma 2.1. Let G = L(H). Then vector spaces E_{0}(G) (≅ Ê(H)) and E^{+}(H) are isomorphic.

Proof. Let, for short, B = B(H) and A = A(G). We have already seen that B^{T} B = A + 2I. If x ∈ Ê(G), then Ax = 0 and B^{T} Bx = 2x. Thus (by pre-multiplying the latter by y^{T}, where y ∈ Ê(G)) we get (By)^{T} (Bx) = 2y^{T} x. Furthermore, if y = x then ∥Bx∥ = \sqrt{2} ∥x∥. Therefore, Bx ≠ 0 if and only if x ≠ 0. Hence B is an injective linear transformation and thus an isomorphism as required. So the proof follows. □

Remark 2.1. It is also interesting that B(H), as a mapping from Ê(H) onto E^{+}(H), preserves the angles, but not the lengths. On the other hand, if we take B′(H) = \frac{1}{\sqrt{2}}B(H), then the scalar product will be preserved (note that (B′(H)y)^{T} (B′(H)x) = y^{T} x), and consequently the lengths as well. □

Lemma 2.1 establishes that, via E_{0}(G) we are able to relate Ê(H) in E^{+}(H) Thus we can focus on the root graph H only.

Assume henceforth that x and y are vectors in Ê(H) and E^{+}(H), respectively, and that y = B(H)x. We have already noted, how the components of y are related to the components of x. We will now examine the converse relationship.

Lemma 2.2. Given x ∈ Ê(H), then y(v) = ∑_{e∼v} x(e). Conversely, given y ∈ E^{+}(H), and e = uv, we have

x(e) = \frac{y(u) + y(v)}{2}.

Proof. The first part follows from y = Bx, where B = B(H). To prove the second part, consider the relation B^{T} Bx = 2x (taken from the proof of Lemma 2.1). Thus we get B^{T} y = 2x, and the result immediately follows. □

Remark 2.2. We can use Lemma 2.2 to get more general results for the components of y.

Firstly, assume that u_{0}, u_{1}, …, u_{k} is a walk in H starting from v = u_{0} and terminating in w = u_{k}. Then we have:

y(w) − (−1)^{k}y(v) = 2 ∑_{i=0}^{k−1}(−1)^{i}x(u_{i}u_{i+1}). (2.1)

To see this, we observe that y(u_{i}) + y(u_{i+1}) = 2x(u_{i}u_{i+1}), for each i = 0, 1, …, k (see Lemma 2.2). After multiplying each of these relations with (−1)^{i}, and summing in i over the above range, the required result follows.

Secondly, assume that u is any vertex of H and v_{1}, v_{2}, …, v_{k} its neighbours (here k = deg(u)). Then by Lemma 2.2, we have:

(deg(u) − 2)y(u) + ∑_{i=1}^{k} y(v_{i}) = 0. (2.2)

To see this, we observe that (by Lemma 2.2) y(u) + y(v_{i}) = 2x(uv_{i}), for each i = 1, 2, …, k. Summing these relations in i over the above range, we obtain (2.2). □

We will now assume that H is a tree with a singular line graph, i.e., an LS. Then we have:

Lemma 2.3. If T is an LS tree and y ∈ E^{+}(T) ∖ {0}, then y(v) ≠ 0 for all v ∈ V (T). In addition, all components of y can be chosen to be odd integers.

Proof. Recall, y = B(T)x for some x ∈ Ê(T) ∖ {0}. Since x is, in fact, an eigenvector of L(T) for an integral eigenvalue (i.e., for λ = 0), we can assume that all components of x are integers. Next, we can also assume that they are relatively prime, i.e., that their greatest common divisor is one (otherwise, this follows by an appropriate scaling). On the other hand, for any edge, say uv, of T we have y(u)+y(v) = 2x(uv) (by Lemma 2.2). Thus, y(u) and y(v) are of the same parity, whenever u and v are adjacent. But since T is connected, the same follows at once for any two vertices of T (see also (2.1)). Now, if all entries of y are odd, we are done. Otherwise, assume that all entries of y are even. Consider next the entries of x. Then, at least one entry is odd (otherwise, their greatest common divisor is not one), and let, say e_{1} = vw_{1}, be an edge for which x(e_{1}) is odd. Since y(w_{1}) is even and B(T)x = y, there exists an edge incident to w_{1}, say e_{2} = w_{1}w_{2} (≠ e_{1}), for which x(e_{2}) is also odd. Next, since y(w_{2}) is even, there exists an edge incident to w_{2}, say e_{3} = w_{2}w_{3} (≠ e_{2}), for which x(e_{3}) is also odd. Repeating this procedure, after some number of steps, we will end up, since T is finite, with a hanging edge, say e_{h} = w_{h−1}w_{h} (≠ e_{h−1}), for which x(e_{h}) is also odd. But then y(w_{h}) (= x(e_{h})) is odd, a contradiction. This completes the proof. □

We will now give results which are direct consequences of the ones above. The first one is the main theorem of [5] (see also [7]).

Theorem 2.1. If T is a tree, then the nullity of L(T) is at most one.

Proof. Assume for contradiction, that the nullity of L(T), or equivalently the dimension of Ê(T), is at least two. But then, by Lemma 2.1, the same applies for E^{+}(T). Consider next two linearly independent vectors in E^{+}(T). Now we can easily construct their linear combination in which at least one entry is zero (but, of course, not all). But this contradicts Lemma 2.3, and the proof follows. □

We give a new proof of the following theorem, which is also proved in [7, Theorem 4.4].

Theorem 2.2. If T is an LS tree, then its order (i.e., the number of vertices) is even.

Proof. For any graph G, since Bx = y, then in particular y(u) = x(e) for an end-vertex u and y(v) = ∑_{v∼e} x(e).

Summing over all vertices of a tree T we get

∑_{v∈V (T)} y(v) = 2 ∑_{e∈E(T)} x(e).

For an LS tree, if x is taken to have the minimal integral norm (as in the proof of Lemma 2.3), then all components of y are odd, and the proof immediately follows. □

Remark 2.3. Suppose that T is an LS tree, and e is one of its edges. Let T_{1} and T_{2} be the components of T − e. Denote by n_{1} and n_{2} the orders of T_{1} and T_{2}, respectively. Notice that n_{1} and n_{2} are of the same parity (by Theorem 2.2). We also assume (due to scaling) that the entries of x are relatively prime (so all the components of y are odd). By using the same arguments as in the proof of Theorem 2.2, we can show that x(e) is even (or odd) if and only if n_{1} and n_{2} are even (resp. odd). So, in particular, all hanging edges of T have odd weights if x is chosen as above. □

Theorem 2.3. If x ∈ Ê(T)∖{0} where T is an LS tree, then all hanging edges attached to the same vertex (of T) have the same weights with respect to x. In addition, all these weights are non-zero.

Proof. Observe first that the collection of hanging edges at some vertex of T gives rise in L(T) to a collection of co-duplicate vertices in L(T). Then, in the corresponding λ-eigenvector (for λ = −1), all entries can be taken to be equal to zero, except for two which correspond to a pair of co-duplicate vertices, where these two entries are equal in modulus, but of opposite signs. Now the result easily follows by the orthogonality of eigenvectors (of L(T)) corresponding to distinct eigenvalues. So, in particular, it holds for λ = 0. The rest of the proof is based on Lemma 2.3. Namely, if e is a hanging edge, then x(e) = 0 would imply y(u) = 0 where u is a terminal vertex of e (here, x and y are interpreted as usual). So the proof follows. □

3. Constructions and reductions

In this section we will consider the possibility of constructing new LS trees from the smaller ones. These constructions will also open an inverse problem, i.e., of reducing the LS trees to some simpler, or basic forms.

Our first construction is based on introducing an edge (or a bridge) between two copies of LS trees.

Theorem 3.1. Let T_{1} and T_{2} be two LS trees, and let T be a tree obtained from the (disjoint) union of T_{1} and T_{2} by connecting them by an edge e. Then T is an LS tree for any choice of e.

Proof. Let e = u_{1}u_{2}, where u_{1} and u_{2} are vertices belonging to T_{1} and T_{2}, respectively. Let x_{1} and x_{2} be 0-eigenvectors of L(T_{1}) and L(T_{2}), respectively. Next, assume that y_{1} = B(T_{1})x_{1} and y_{2} = B(T_{2})x_{1}. With an appropriate choice of x_{1} and x_{2} (and with some scaling if necessary – see also Lemma 2.3), we can assume that y_{1}(u_{1}) + y_{2}(u_{2}) = 0. Define next x as follows:

x(f) = \{ \begin{matrix}0 & f = e, \\ x_{1}(f) & f ∈ E(T_{1}), \\ x_{2}(f) & f ∈ E(T_{2}). \end{matrix} (3.1)

It is now a matter of routine to check that x is a 0-eigenvector of L(T). This completes the proof. □

Remark 3.1. From this theorem, we can easily deduce that any tree T with a perfect matching is an LS tree. To see this, observe first that K_{2} is an LS tree; observe next that any tree with a perfect matching can be constructed starting from K_{2} by adding in turns (like in Theorem 3.1) a copy of K_{2} to the previously constructed trees. □

From the proof of Theorem 3.1 (see (3.1)) we have that x(e) = 0 whenever x ∈ E_{0}(T) (see also Theorem 2.1). In view of this situation, we can say that some edge of an LS tree is light (heavy) if the corresponding entry in x is zero (resp. non-zero). In addition, any LS tree T without light edges will be called a heavy tree (note, then L(T) is a nut graph, according to [7]).

We will now establish a criterion for distinguishing light from heavy edges in LS trees. Then we can split some non-heavy LS tree to smaller ones (which can be all heavy) – this can be viewed as a reduction of LS trees.

Theorem 3.2. Let T be an LS tree, and e any of its edges. Then e is a light edge (of T) if and only if both components of T − e are LS trees.

Proof. In view of Remark 3.1, we have only to prove one half of the claim. For this purpose, assume that e is a light edge. If so, then the angle^{1} (in L(T)) corresponding to the eigenvalue 0 for the vertex originating from the edge e (of T) is 0. Therefore, by interlacing, the multiplicity of 0 in L(T − e) is at least one, but at most two (note, in L(T) it was one, and in general it can change by one at most in any vertex deleted subgraph; in addition, it cannot be 0 since the angle in question is 0; see [3, Chapter 7]). So, at least one of the components of T − e is an LS tree. Assume next that both components are not LS trees. In other words, if T − e = T_{1} ∪ T_{2}, assume that, say T_{1}, is an LS tree, but not T_{2}. Let x_{1} and x_{2} be the vectors obtained as restrictions of x, the 0-eigenvector of L(T), to the edges of T_{1} and T_{2}, respectively. If so, x_{2} = 0. Next, let u_{2} be the vertex of T_{2} incident to e. But then, since y = B(T)x), y(u_{2}) = 0, a contradiction (by Lemma 2.3).

This completes the proof. □

1See [2, Chapter 4].

Remark 3.2. Note that in line graphs of LS trees, the multiplicity of 0 in any vertex-deleted subgraph is either zero or two. □

In what follows we will focus our attention only on heavy LS trees. For these trees, we have the following structural restriction.

Corollary 3.1. If T is a heavy LS tree, then it has no hanging paths of length greater than one.

Proof. Assume for contradiction that P is a hanging path of T whose length is at least two. Let ee be the edge of P which is adjacent to some hanging edge. It is now easy to see (by Theorem 3.2) that e is a light edge, and consequently, T is not a heavy tree. So the proof follows. □

We will now consider another possibility for getting new LS trees from some known ones (which are not necessarily heavy ones). The basic idea consists in a twophase modification of some LS tree. The first phase is a vertex splitting. (Recall, by splitting a vertex, say u (in any graph G), we understand the following two steps:

(i) deletion of u from G along with all incident edges; (ii) adding (to G − u) two vertices, say u_{1} and u_{2}, and, for each edge uv of G, adding one edge which is equal to either u_{1}v or u_{2}v (but not both). Note that if E(u) is a set of edges incident to u, then a vertex splitting is determined by a bipartition E_{1}(u) ˙∪E_{2}(u); then if uv ∈ E_{i}(u) (i = 1 or 2), this means that an edge u_{i}v is added in step (ii)). The second phase is related to an one-vertex extension. Namely, we then add a vertex, say w, adjacent only to vertices u_{1} and u_{2} (from (i)).

Lemma 3.1. Let T be an LS tree, and T′ a tree obtained from T by a two-step modification described above. Then T′ is an LS tree.

Proof. Under the above notation, let e_{1} = u_{1}w and e_{2} = u_{2}w (w is the vertex as in (ii) above). For the sake of simplicity, we will assume that the edges of T′ incident with u_{1} or u_{2} are viewed as the edges of T incident to u. Then, the edges of T′ are E(T) ∪ {e_{1}, e_{2}}. Assume next that x is a 0-eigenvector of L(T), and that E(u), the set of edges of T incident to u, is divided into two disjoint subsets E_{1}(u) and E_{2}(u) as above). Define then a vector x′ (on the edge set of T′) as follows:

x′(e) = \{ \begin{matrix}x(e) & e ∈ E(T), \\ −_{∑f∈E_{2}(u)}x(f) & e = e_{1}, \\ −_{∑f∈E_{1}(u)}x(f) & e = e_{2}. \end{matrix}

Now it is a matter of routine to check that the vector x′ is a 0-eigenvector for L(T′). So the proof follows. □

Remark 3.3. Notice first that the two-phase modification of an LS tree T in which E_{1}(u) or E_{2}(u) is a singleton, is equivalent to the subdivision (by inserting two vertices) of one of the edges (of T) incident to u. Notice also that there is no need (see Corollary 3.1) to subdivide hanging edges of LS trees – for otherwise, we get trees which are not heavy. Therefore, we will consider, further on, only the subdivisions of edges which lie in internal paths. (Recall that an internal path of any graph, not necessarily a tree, is a path between two fixed vertices which are both of degree at least three, while all other vertices between them (if any) are of degree two.) □

We will now ask when the resulting LS trees (obtained by the two-phase modification of LS trees) are heavy. By inspecting the proof of Lemma 3.1 get:

Corollary 3.2. Let T be an LS tree, and let T′ be a tree obtained by a twophase modification of T with respect to u. Then T′ is a heavy LS tree if and only if T is heavy and ∑_{e∈E_{i}(u)} x(e) ≠ 0 (i = 1 and 2).

We will now turn to reductions. We will focus on deleting vertices of degree two from LS trees. In the sequel, · stands for coalescence (or dot product) G · H of two rooted graphs G and H (obtained by identifying a vertex of G with a vertex of H).

Theorem 3.3. Let T be an LS tree, and let u be a vertex (of T) of degree two having u_{1} and u_{2} as its neighbours. Let T_{u_{1}} and T_{u_{2}} be the components of T − u with u_{1} and u_{2} as its roots. Then T_{u_{1}} · T_{u_{2}} is an LS tree. Moreover, it is a heavy LS tree if and only if T is a heavy LS tree.

Proof. Let x be a 0-eigenvector of L(T). Set a = ∑_{v∼u_{1},v≠u} x(u_{1}v) and b = ∑_{v∼u_{2},v≠u} x(u_{2}v). Now we have (by the eigenvalue equations) that x(uu_{2}) = −a and x(uu_{1}) = −b. Consider now the vector x′ constructed as follows:

x′(e) = \{ \begin{matrix}x(e) & e ∈ E(T_{u_{1}}), \\ −x(e) & e ∈ E(T_{u_{2}}). \end{matrix}

It is now a matter of routine to check that the vector x′ is a 0-eigenvector of L(T′). The rest of the proof immediately follows. □

Remark 3.4. In Corollary 3.2, we have seen that the two-phase modification of a heavy LS tree T with respect to vertex u need not be a heavy LS tree. In fact, if ∑_{e∈E_{1}(u)} x(e) = 0, while ∑_{e∈E_{2}(u)} x(e) ≠ 0 (note, by Lemma 2.3, the sums cannot be both equal to zero) then the edge e = wu_{2} (in T′) is light. Consequently, T′ − e = T_{1} ∪ T_{2} consists (by Theorem 3.2) of two LS trees. The first tree has at the vertex u_{1} a hanging edge f = u_{1}w; if we look at T then we see that it is equal to (T_{1} − w)_{u_{1}} · (T_{2})_{u_{2}}. So, it follows that a hanging edge of some LS tree is replaced by an arbitrary LS tree (in forming T), or that T is (after some local modification) splitted into two smaller LS trees. Furthermore, we will call LS trees which do not allow splitting into smaller LS trees by a two-phase modification, virreducible trees. In this context, heavy LS trees (without light edges) will be called e- irreducible trees. □

In view of Theorem 3.3 and Remark 3.4, LS trees which do not have vertices of degree two, and which are both v-irreducible and e-irreducible, will be called basic LS trees.

B_{1}  B_{2}  B_{3}  B_{4} B_{5}  B_{6}  B_{7} B_{8}  B_{9} B^{10}  B^{11}

Figure 2. Basic LS trees up to 20 vertices

4. Basic LS trees with up to 20 vertices

In this section we will give some results obtained by a computer search. More precisely, we will list all basic LS trees with up to 20 vertices. These results are depicted in Fig. 2.

Remark 4.1. There are 970 100 trees with an even number of vertices on up to 20 vertices. We have extracted from among these trees only 11 basic LS trees. Thus the property of being a basic LS tree seems to be a very rare phenomenon. □

In the next section we will give further basic LS trees obtained by constructions (which are inspired by the considerations from this and former sections).

5. Some further considerations

In this section, we consider problems related to considerations from the previous sections.

Firstly, we can ask whether the collection of basic LS trees is finite or not. With respect to our definition of basic LS trees the answer is negative. The following two LS trees (see Fig. 3) are basic for every k ⩾ 1 (this can be easily checked by constructing the corresponding eigenvector). They are all extensions of the LS tree on 10 vertices depicted in Fig. 2. Since k is unbounded, we have constructed an infinite family of basic LS trees.

k } k + 1  k + 1  2k + 1  k }

Figure 3. Two series of basic LS trees.

Problem 5.1. Are there other reductions (and constructions) which can be used to extend the definition of basic LS trees so that we get a finite set of “basic” LS trees? □

Secondly, we can consider generalized line graphs. We first note that any petal gives rise to a pair of duplicate vertices. In particular, if Ĥ is a tree with petals, then G (= L(Ĥ)) has nullity equal at most to the number of petals (in the root graph). This bound is increased by one if Ĥ with the petals replaced by an edge is an LS tree. However, if the root graph gives rise to a non-singular line graph upon the deletion of one edge from each petal, then the nullity is equal to the number of petals in Ĥ. For example, if the number of vertices of the tree in question is odd, we get, for any number of petals, that the corresponding generalized line graph has a rank property, that is its adjacency matrix gets a full rank if all duplicate vertices are deleted. So we have here obtained (at least partially) one natural class of graphs for which the rank property holds (cf. Question 4.1, from [9]).

References

[1] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Applications, III revised and enlarged edition, Johan Ambrosius Bart. Verlag, Heidelberg–Leipzig, 1995.

[2] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs, Cambridge University Press, 1997.

[3] D. Cvetković, P. Rowlinson, S. Simić, Spectral Generalizations of Line Graphs – On graphs with least eigenvalue −2, Cambridge University Press, 2004.

[4] M. Ellingham, Basic subgraphs and graph spectra, Australasian J. Comb. 8 (1993), 247–265.

[5] I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232 (2001), 35–45.

[6] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969.

[7] I. Sciriha, On singular line graphs of trees, Congr. Numer. 135 (1998), 73–91.

[8] I. Sciriha, The two classes of singular line graphs of trees, Rend. Sem. Mat. Messina, Ser II,5 (1999), 167–180.

[9] G. F. Royle, The rank of a cograph, Electron. J. Comb. 10 (2003), #N11.

Department of Mathematics (Received 09 12 2005) Faculty of Electrical Engineering (Revised 22 08 2006) University of Messina Messina, Italy

marino@ingegneria.unime.it

Department of Mathematics Faculty of Science University of Malta Msida MSD 06, Malta

irene.sciriha-aquilina@um.edu.mt

Department of Mathematics Faculty of Computer Science 11000 Belgrade, Serbia

ssimic@raf.edu.yu

School of Electrical Engineering University of Belgrade 11000 Belgrade, Serbia

tosic@etf.bg.ac.yu