PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 63 (77), 1998, 31–36

DISTANCE OF THORNY GRAPHS

Ivan Gutman

Communicated by Slobodan Simić

Abstract. Let G be a connected graph on n vertices. The thorn graph G^{⋆} of G is obtained from G by attaching to its i-th vertex p_{i} new vertices of degree one, p_{i} ≥ 0 , i = 1, 2,…, n. Let d(G) be the sum of distances of all pairs of vertices of G. We establish relations between d(G) and d(G^{⋆}) and examine several special cases of this result. In particular, if p_{i} = γ − γ_{i}, where γ is a constant and γ_{i} the degree of the i-th vertex in G, and if G is a tree, then there is a linear relation between d(G^{⋆}) and d(G) , namely d(G^{⋆}) = (γ − 1)^{2} d(G) + [(γ − 1)n + 1]^{2} .

Introduction

In this paper we consider connected finite graphs without loops and multiple edges. Let G be such a graph, V = V (G) its vertex set, E = E(G) its edge set, and let its vertices, whose number is n, be labeled by u_{1}, u_{2},…, u_{n}. The distance (= length of a shortest path) between the vertices u_{i} and u_{j} of G is denoted by d(u_{i}, u_{j}|G) . The sum of the distances between all pairs of vertices of G is the distance of the graph G and is denoted by d(G) .

In the mathematical literature the distance of a graph was first introduced by Entringer, Jackson and Snyder [2], although the chemical applications of this quantity are somewhat older [8]. For results concerning the distance of compound graphs as well as for additional references see [3,6,9].

Let p_{1}, p_{2},…, p_{n} be non-negative integers.

Definition 1. The thorn graph of the graph G, with parameters p_{1}, p_{2},…, p_{n}, is obtained by attaching p_{i} new vertices of degree one to the vertex u_{i} of the graph G, i = 1, 2,…, n.

The thorn graph of the graph G will be denoted by G^{⋆}, or if the respective parameters need to be specified, by G^{⋆}(p_{1}, p_{2},…, p_{n}) .

AMS Subject Classification (1991): Primary 05C12 Supported by Ministry of Science and Technology of Serbia, grant number 04M03/C

In this work we examine the relation between d(G) and d(G^{⋆}) . The motivation for this study comes from a particular special case, namely G^{⋆}(γ − γ_{1}, γ − γ_{2},…, γ − γ_{n}) , where γ_{i} is the degree of the i-th vertex of G and γ is a constant (γ ≥ γ_{i} for all i = 1, 2,…, n). Then the vertices of G^{⋆} are either of degree γ or of degree one. If, in addition, γ = 4 , then the thorn graph is just what Cayley [1] calls a “plerogram” and Pólya [7] a “C–H graph”. (The parent graph G would then be referred to as a “kenogram” [1] or a “C–graph” [7]. Clearly, these notions have their origins in the attempts to represent molecular structure by means of graphs [4].) It is also worth mentioning that the so–called “caterpillars” [5] are thorn graphs whose parent graph is a path.

Denote the vertex set of G^{⋆} by V^{⋆}. Further, the set of degree–one vertices of G^{⋆}, attached to the vertex u_{i} is V_{i}. Its cardinality is p_{i} and, clearly,

V^{⋆} = V ∪ V_{1} ∪ V_{2} ∪ ⋯ ∪ V_{n} and V_{i} ∩ V_{j} = ∅ for i ≠ j

The main results

Let {x, y} ⊆ V^{⋆}. In order to compute d(G^{⋆}) we distinguish between four types of pairs of vertices of G^{⋆}: Type 1. x ∈ V , y ∈ V ; Type 2. x ∈ V_{i} , y ∈ V , for some i , 1 ≤ i ≤ n ; Type 3. x ∈ V_{i} , y ∈ V_{j} , for some i, j , 1 ≤ i < j ≤ n ; Type 4. x ∈ V_{i} , y ∈ V_{i}, for some i , 1 ≤ i ≤ n .

Let the contributions of all such vertex pairs to d(G^{⋆}) be denoted by F_{1} , F_{2} , F_{3} and F_{4} , respectively. Then,

d(G^{⋆}) = F_{1} + F_{2} + F_{3} + F_{4}  (1)

If {x, y} is a vertex pair of Type 1, then d(x, y|G^{⋆}) = d(x, y|G) and therefore

F_{1} = d(G)

There are p_{i} vertex pairs {x, y} of Type 2, and for each of them d(x, y|G^{⋆}) = d(u_{i}, y|G) + 1 . Therefore

F_{2} = ∑_{i=1}^{n} ∑_{y∈V} p_{i} [d(u_{i}, y|G) + 1] = ∑_{1≤i<j≤n}(p_{i} + p_{j}) d(u_{i}, u_{j}|G) + n ∑_{i=1}^{n} p_{i}

There are p_{i} · p_{j} vertex pairs {x, y} of Type 3, and for each of them d(x, y|G^{⋆}) = d(u_{i}, u_{j}|G) + 2 . Therefore

F_{3} = ∑_{1≤i<j≤n} p_{i} p_{j} [d(u_{i}, u_{j}|G) + 2] = ∑_{1≤i<j≤n} p_{i} p_{j} d(u_{i}, u_{j}|G) + (∑_{i=1}^{n} p_{i})^{2} − ∑_{i=1}^{n} p_{i}^{2}

There are \binom{p_{i}}{2} vertex pairs \{x, y\} of Type 4, each of them at distance 2 . Therefore

F_{4} = ∑_{i=1}^{n} 2 \binom{p_{i}}{2} = ∑_{i=1}^{n} p_{i}^{2} − ∑_{i=1}^{n} p_{i}

Substituting the above relations back into Eq. (1) we arrive at the general expression for the distance of a thorn graph:

Theorem 1. If G^{⋆} is the thorn graph of the graph G, with parameters p_{i} , p_{i} ≥ 0 , i = 1, 2,…, n, then

d(G^{⋆}) = d(G) + ∑_{1≤i<j≤n}(p_{i} + p_{j}) d(u_{i}, u_{j}|G) + ∑_{1≤i<j≤n} p_{i} p_{j} d(u_{i}, u_{j}|G)

+ (∑_{i=1}^{n} p_{i})^{2} + (n − 1) ∑_{i=1}^{n} p_{i}  (2)

i.e.,

d(G^{⋆}) = ∑_{1≤i<j≤n}(p_{i} + 1)(p_{j} + 1) d(u_{i}, u_{j}|G) + (∑_{i=1}^{n} p_{i})^{2} + (n − 1) ∑_{i=1}^{n} p_{i} (3)

Corollary 1.1. If G^{⋆} is the thorn graph of the graph G, with parameters p_{1} = p_{2} = ⋯ = p_{n} = p, then d(G^{⋆}) and d(G) are related as:

d(G^{⋆}) = (p + 1)^{2} d(G) + np(np + n − 1)

Theorem 1 has been obtained by a routine combinatorial reasoning and the form of Eqs. (2) and (3) is neither appealing nor unexpected. Also, the existence of a simple linear connection between d(G^{⋆}(p, p,…, p)) and d(G) , as specified in Corollary 1.1, is by no means a surprise. The following two special cases seem, however, to be somewhat less self–evident and hardly could have been anticipated.

Let T be an n-vertex tree and let γ_{i} be the degree of its i-th vertex. Recall that

γ_{1} + γ_{2} + ⋯ + γ_{n} = 2n − 2

Corollary 1.2. If T^{⋆} is the thorn graph of the tree T , with parameters p_{i} = γ_{i} , i = 1, 2,…, n, then d(T^{⋆}) and d(T) are related as:

d(T^{⋆}) = 9 d(T) + (n − 1)(3n − 5)

Corollary 1.3. Let γ be an integer with the property γ ≥ γ_{i} , i = 1, 2,…, n. If T^{⋆} is the thorn graph of the tree T , with parameters p_{i} = γ −γ_{i} , i = 1, 2,…, n, then d(T^{⋆}) and d(T) are related as:

d(T^{⋆}) = (γ − 1)^{2} d(T) + [(γ − 1)n + 1]^{2}

Proofs

Theorem 1 has already been verified, and Corollary 1.1 is immediate. What remains is to demonstrate the validity of Corollaries 1.2 and 1.3. For this we need:

Lemma 1. If T is a tree on n vertices u_{1}, u_{2},…, u_{n} and if the degree of u_{i} is γ_{i} , i = 1, 2,…, n, then

∑_{1≤i<j≤n}(γ_{i} + γ_{j}) d(u_{i}, u_{j}|T) = 4 d(T) − n(n − 1)  (4)

and

∑_{1≤i<j≤n} γ_{i} γ_{j} d(u_{i}, u_{j}|T) = 4 d(T) − (n − 1)(2n − 1)  (5)

Proof. Let V (T) and E(T) be the vertex and edge sets, respectively, of the tree T . Let e ∈ E(T) . Then the subgraph whose vertex set is V (T) and whose edge set is E(T) \ {e} consists of two components, T_{1} = T_{1}(e) and T_{2} = T_{2}(e) , possessing n_{1} = n_{1}(e|T) and n_{2} = n_{2}(e|T) vertices, respectively. Recall that n_{1}(e|T) + n_{2}(e|T) = n holds for all e ∈ E(T) .

It is long known [8] that the distance d(T) of a tree T (in which the path between any two vertices is unique) may be calculated by counting the paths of T which contain the edge e, and summing this count over all edges of T . Now, the number of paths of T containing e is n_{1}(e|T) · n_{2}(e|T) and therefore,

d(T) = ∑_{e∈E(T)} n_{1}(e|T) n_{2}(e|T)  (6)

which may be rewritten as

d(T) = ∑_{e∈E(T)} ∑_{u_{i}∈V (T_{1})} ∑_{u_{j}∈V (T_{2})} 1  (7)

Associate to each pair of vertices u_{i}, u_{j} ∈ V (G) a weight ω_{ij} and define a generalized distance–sum d_{ω}(G) as

d_{ω}(G) = ∑_{1≤i<j≤n} ω_{ij} d(u_{i}, u_{j}|G)

Clearly, if ω_{ij} = 1 for all i, j , 1 ≤ i < j ≤ n then d_{ω}(G) = d(G) .

Now, repeating the reasoning leading to Eq. (7), and bearing in mind that for T being a tree, in d_{ω}(T) the distance between the vertices u_{i}, u_{j} has to be counted with weight ω_{ij}, we obtain

d_{ω}(T) = ∑_{e∈E(T)} ∑_{u_{i}∈V (T_{1})} ∑_{u_{j}∈V (T_{2})} ω_{ij}  (8)

If we choose ω_{ij} = γ_{i} + γ_{j} then Eq. (8) yields

∑_{1≤i<j≤n}(γ_{i} + γ_{j}) d(u_{i}, u_{j}|T) = ∑_{e∈E(T)} [n_{2} ∑_{u_{i}∈V (T_{1})} γ_{i} + n_{1} ∑_{u_{j}∈V (T_{2})} γ_{j}] (9)

Because T_{1} and T_{2} have n_{1} − 1 and n_{2} − 1 edges, respectively,

∑_{u_{i}∈V (T_{1})} γ_{i} = 2(n_{1} − 1) + 1  (10)

and

∑_{u_{j}∈V (T_{2})} γ_{j} = 2(n_{2} − 1) + 1  (11)

Recall that γ_{i} and γ_{j} in Eqs. (10) and (11) are the degrees of the vertices of the tree T ; they coincide with the degrees of the vertices of the trees T_{1} and T_{2} , respectively, except for one particular vertex of T_{1} and for one particular vertex of T_{2} . These “exceptional” vertices of T_{1} and T_{2} have degrees by one less than in T . The terms +1 on the right–hand sides of Eqs. (10) and (11) occur because of this difference between the vertex degrees of T and the vertex degrees of T_{1} and T_{2}.

Substituting (10) and (11) back into Eq. (9) results in

∑_{1≤i<j≤n}(γ_{i} + γ_{j}) d(u_{i}, u_{j}|T) = ∑_{e∈E(T)}[4 n_{1} n_{2} − (n_{1} + n_{2})]  (12)

Using the fact that T has n − 1 edges, that n_{1} + n_{2} = n and that d(T) obeys Eq. (6), Eq. (4) is directly obtained from Eq. (12).

This proves the first part of Lemma 1.

If, on the other hand, we choose ω_{ij} = γ_{i} · γ_{j} , then from Eq. (8),

∑_{1≤i<j≤n} γ_{i} γ_{j} d(u_{i}, u_{j}|T) = ∑_{e∈E(T)} [ ∑_{u_{i}∈V (T_{1})} γ_{i}] [ ∑_{u_{j}∈V (T_{2})} γ_{j}]

= ∑_{e∈E(T)}[2(n_{1} − 1) + 1][2(n_{2} − 1) + 1]

Combining the above with Eq. (6) leads to Eq. (5).

This completes the proof of Lemma 1. □

Proof of Corollary 1.2. Set p_{i} = γ_{i} into Eq. (1) and use Eqs. (4) and (5) of Lemma 1. □

Proof of Corollary 1.3. Set p_{i} = γ − γ_{i} into Eq. (1) and use Lemma 1. The calculation is somewhat lengthier than, but fully analogous to the previous case. □

References

[1] A. Cayley, On the mathematical theory of isomers, Phil. Magazine 47 (1874), 444–446.

[2] R. C. Entringer, D. E. Jackson, D. A. Snyder, Distance in graphs, Czech. Math. J. 26 (1976), 283–296.

[3] I. Gutman, On the distance of some compound graphs, Publ. Elektrotehn. Fak. (Beograd) Ser. Mat. 5 (1994), 29–34.

[4] I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer–Verlag, Berlin, 1986, pp. 19–20.

[5] F. Harary, A. J. Schwenk, The number of caterpillars, Discrete Math. 6 (1973), 359–365.

[6] J. Plesnik, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984), 1–21.

[7] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254, sections 35–37, 55.

[8] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17–20.

[9] Y. N. Yeh, I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994), 359–365.

Prirodno-matematički fakultet (Received 19 08 1997) Univerzitet u Kragujevcu 34000 Kragujevac, p.p. 60 Yugoslavia