Skip to main content

Bounds on the number of closed walks in a graph and its applications

Abstract

Using graph-theoretical techniques, we establish an inequality regarding the number of walks and closed walks in a graph. This inequality yields several upper bounds for the number of closed walks in a graph in terms of the number of vertices, number of edges, maximum degree, degree sequence, and the Zagreb indices of the graph. As applications, we also present some new upper bounds on the Estrada index for general graphs, bipartite graphs, trees and planar graphs, some of which improve the known results obtained by using the algebraic techniques.

MSC:05C50, 94C15, 05C38.

1 Introduction

Throughout this paper we consider simple graphs, i.e., graphs without loops and multiple edges. For a graph G with n (n2) vertices, the adjacency matrix of G is, as usual, defined as the n×n matrix A(G)=[ a i j ] in which a i j =1 if the i th and the j th vertices are adjacent, and a i j =0 otherwise. The eigenvalues of A(G) are also called the eigenvalues of the graph G. For a vertex v in G, we denote by N(v) and d(v) the neighbor (the set of vertices adjacent to v) and the degree of v, respectively. The degree sequence of G, denoted by ( d 1 , d 2 ,, d n ), is a list of the vertex degrees of G in non-increasing order. Let V(G) and E(G) denote the vertex set and edge set of G, respectively. The first and the second Zagreb indices of G are defined as

Z g 1 (G)= v V ( G ) d 2 (v)andZ g 2 (G)= u v E ( G ) d u d v ,

respectively [1].

A walk W of length k starting at a vertex v 0 and ending at a vertex v k in G is a sequence of vertices, i.e., v 0 v 1 v 2 v k , in which v i is adjacent to v i + 1 for each i=0,1,,k1. In particular, if the vertices v 0 , v 1 , v 2 ,, v k (except the possible v 0 and v k ) are pairwise distinct, then W is well known as a path, and if v 0 = v k then W is called a closed walk. It is well known [2] that the number of closed walks of length k in G is exactly the trace of A ( G ) k which, in turn, is the sum of the k th power of the eigenvalues of G (known as the k th spectral moment of G). This fact is of importance in the theory of total π-electron energy, for details see [3, 4] and the references cited therein. Also, the sequence of the numbers of closed walks of length k, k=1,2, , starting at a given vertex v, was proposed by Randić [5] for characterization of the environment of vertex v.

Based on the number of closed walks, Estrada [6] put forward a graph invariant, which was originally referred to as the subgraph centrality but has since become known as the Estrada index of a graph G, defined as

EE(G)= i = 1 n e λ i ,

where λ 1 , λ 2 ,, λ n are the eigenvalues of G. The Estrada index has successfully found applications in various fields, including biochemistry [6, 7] and complex networks [8]. Also, a number of mathematical properties, especially various lower and upper bounds on the Estrada index of a graph have been established, for details we refer the reader to [916]; other properties can be found in [1719] and a latest survey paper by Gutman et al. [20].

In general, counting the closed walks in a graph (of large order) is not an easy work. Only a few results were obtained for some special types of graphs, e.g., vertex-transitive graphs [21] and generalized de Bruijn graphs [22]. In this paper, using graph-theoretical techniques, we establish an inequality regarding the number of walks and closed walks starting at a given vertex. This inequality yields several upper bounds for the number of closed walks in a graph in terms of the number of vertices, number of edges, maximum degree, degree sequence, the first and the second Zagreb indices of the graph. As applications, in Section 3 we present some new upper bounds on the Estrada index for general graphs, bipartite graphs, trees, and planar graphs, which improve some known results obtained by using the algebraic techniques.

2 Main results

Given a graph G and a vertex v, let W k (G,v) denote the set of walks of length k starting at v in G, and let W k (G,v)=| W k (G,v)|. Obviously, W 0 (G,v)=1, W 1 (G,v)=d(v). Moreover, it is easy to check that

W 2 ( G , v ) = u N ( v ) d ( u ) , W 3 ( G , v ) = u N ( v ) w N ( u ) d ( w ) .

In general, we have the following result.

Lemma 1 Let G be a graph of order n with maximum degree Δ, and let v be an arbitrary vertex in G. Then

W k (G,v) Δ k ,for any k1,
(1)
W k (G,v)d(v) Δ k 1 ,for any k2,
(2)
W k (G,v) u N ( v ) d(u) Δ k 2 ,for any k3,
(3)
W k (G,v) u N ( v ) w N ( u ) d(w) Δ k 3 ,for any k4.
(4)

Each of the equalities holds in (1)-(4) for all v if and only if G is regular.

Proof Let W=v v 1 v 2 v k be a walk in W k (G,v). Observe that each of k steps of W has at most Δ choices, then (1) follows. We also notice that the first one, two, and three step(s) of W have exactly d(v), u N ( v ) d(u) and u N ( v ) w N ( u ) d(w) choices, respectively, and each of the remaining steps has at most Δ choices, so (2), (3), and (4) follow as well. Moreover, it is not difficult to see that each of the equalities holds in (1)-(4) for all v in G if and only if G is a Δ-regular graph. This completes the proof. □

Let W k (G) be the number of walks of length k in G, i.e., W k (G)= v V ( G ) W k (G,v). It is clear that W 0 (G)=n, W 1 (G)= v V ( G ) d(v)=2m. Moreover, one can deduce easily that

W 2 ( G ) = v V ( G ) u N ( v ) d ( u ) = u V ( G ) d 2 ( u ) = Z g 1 ( G ) , W 3 ( G ) = v V ( G ) u N ( v ) w N ( u ) d ( w ) = u V ( G ) d ( u ) w N ( u ) d ( w ) = 2 u w E ( G ) d ( u ) d ( w ) = 2 Z g 2 ( G ) ,

where Z g 1 (G), Z g 2 (G) are the first and the second Zagreb indices of G, respectively. Using these facts and Lemma 1, for general k1, we have the following.

Theorem 2 Let G be a graph with n vertices, m edges, and maximum degree Δ. Then

W k (G)n Δ k ,for any k1,
(5)
W k (G)2m Δ k 1 ,for any k2,
(6)
W k (G)Z g 1 (G) Δ k 2 ,for any k3,
(7)
W k (G)2Z g 2 (G) Δ k 3 ,for any k4.
(8)

Each of the equalities holds in (5)-(8) if and only if G is regular.

Proof This proof is trivial. □

Remark Bounds (6)-(8) can be seen as some slight improvements of bound (5). Here, we also list two other improvements of bound (5) for using later.

  1. (i)

    [23] Let G be a graph of order n with degree sequence ( d 1 , d 2 ,, d n ). Then for k1,

    W k (G) i = 1 n d i k ,
    (9)

    with equality if and only if G is regular or k2.

  2. (ii)

    [24] Let G be a graph of order n with maximum degree Δ. If G admits an orientation with maximum outdegree dΔ/2, then for k1,

    W k (G)n 2 k d k / 2 ( Δ d ) k / 2 .
    (10)

    Moreover, from the proof of (10) (see Theorem 16 in [24]), one can deduce that the equality holds in (10) if and only if G is a Δ-regular Euler graph.

Now we turn to the number of closed walks. Let CW k (G,v) denote the set of closed walks of length k starting and ending at v in G, and let C W k (G,v)=| CW k (G,v)|. It is obvious that 0=C W 1 (G,v)< W 0 (G,v)=1, C W 2 (G,v)= W 1 (G,v)=d(v). In general, for k3 we establish the following simple but useful result.

Lemma 3 Let G be a graph of order n and let v be an arbitrary vertex in G. Then, for any k3,

C W k (G,v) W k 1 (G,v),
(11)

with equality if and only if k is even, and the component of G containing v is bipartite and v is adjacent to each of the vertices in the other partition part.

Proof Let f be the map from CW k (G,v) into W k 1 (G,v) such that, for any closed walk v v 1 v 2 v k 1 v CW k (G,v),

f(v v 1 v 2 v k 1 v)=v v 1 v 2 v k 1 .

One can see that different closed walks are mapped to different walks by f, which yields

C W k (G,v) W k 1 (G,v).

Further, the equality holds if and only if the end vertex of each walk in W k 1 (G,v) is adjacent to v. In this case, if k is odd then, for any edge vu, W k 1 (G,v) contains a walk of the form W=vuvuvuv while v is not adjacent to itself, a contradiction. So if the equality holds in (11), then k must be even.

Now we consider the component C v of G containing v, under the assumption that the equality holds in (11) and k is even. Let N l (G,v) denote the set of vertices at distance l from v in G. We claim that N l (G,v) is an empty set, for any l3. Otherwise there would be a path P=v v 1 v 2 v 3 such that v 3 is not adjacent to v, but the walk W=v v 1 v v 1 v v 1 v 2 v 3 defined on the path P belongs to W k 1 (G,v), which implies that v 3 is adjacent to v, a contradiction. We next show that there are no edges with both end vertices in N l (G,v), l{1,2}. For contradiction, assume that there is an edge, say v 1 v 2 , with v 1 , v 2 N 1 (G,v). Then T=v v 1 v 2 v is a triangle and consequently the walk W=v v 1 v v 1 v v 1 v 2 v defined on T belongs to W k 1 (G,v), which implies that v is adjacent to v, again a contradiction. Similarly, if there are some edges with both end vertices in N 2 (G,v), then there must exist a path P=v v 1 v 2 v 3 such that v 3 is not adjacent to v, which also yields a contradiction as the above argument. Thus, it follows that the component C v is bipartite with partition ( N 1 (G,v), N 2 (G,v){v}).

The converse is obvious, completing the proof. □

Let C W k (G) denote the number of closed walks of length k in G, i.e., C W k (G)= v V ( G ) C W k (G,v). Clearly, C W 0 (G)=n, C W 1 (G)=0 and C W 2 (G)=2m. For any k3, using Lemma 3, we have

Theorem 4 Let G be a graph of order n with maximum degree Δ and degree sequence ( d 1 , d 2 ,, d n ). Then, for any k3,

C W k (G)n Δ k 1 ,
(12)
C W k (G)2m Δ k 2 ,
(13)
C W k (G)Z g 1 (G) Δ k 3 ,
(14)
C W k (G)2Z g 2 (G) Δ k 4 (for k4),
(15)
C W k (G) i = 1 n d i k 1 .
(16)

Each of the equalities holds in (12)-(16) if and only if k is even and each component of G is the complete bipartite graph K Δ , Δ . Moreover, if G admits an orientation with maximum outdegree dΔ/2, then, for any k3,

C W k (G)n 2 k 1 d ( k 1 ) / 2 ( Δ d ) ( k 1 ) / 2 ,
(17)

with equality if and only if both k and Δ are even and each component of G is the complete bipartite graph K Δ , Δ .

Proof For k3, it follows from Lemma 3 that

C W k (G)= v V ( G ) C W k (G,v) v V ( G ) W k 1 (G,v)= W k 1 (G),

with equality if and only if k is even, and each component of G is a complete bipartite graph. This result together with bounds (5)-(10) yield bounds (12)-(17) directly; also the equality cases follow by noting that G is Δ-regular (Δ is even in the case of (17)). The proof is completed. □

Recall that an orientation of a graph G is a digraph D obtained from G by choosing an orientation for each edge. The outdegree of a vertex v in D is the number of edges with tail v. It is well known [24] that a tree (or forest) admits an orientation with maximum outdegree d=1 and a planar graph with d=3. In fact, for a forest, fixing a root for each component and orienting each edge in each component toward its root would yield an orientation with d=1; furthermore, a planar graph has an orientation with d=3 since its edges can be partitioned into three forests (see, e.g., [25]). Thus, by (17) we get an immediate corollary.

Corollary 5 Let G be a graph of order n with maximum degree Δ. If G is a tree (or forest) and Δ2, then, for any k3,

C W k (G)<n ( 4 ( Δ 1 ) ) k 1 .
(18)

If G is a planar graph and Δ6, then, for any k3,

C W k (G)<n ( 12 ( Δ 3 ) ) k 1 .
(19)

Remark that if G is a bipartite graph (including tree and forest), then there are no closed walks of odd length in G, and hence C W k (G)=0 when k is odd. Formally this is stated in the following proposition.

Proposition 6 Let G be a bipartite graph. Then, for any k1, C W 2 k 1 (G)=0.

3 Applications

In this section we apply the results in the previous section to estimate the Estrada index of graphs.

Let M k (G) denote the k th spectral moment of G, i.e., M k (G)= i = 1 n λ i k , where λ 1 , λ 2 ,, λ n are the eigenvalues of G. Then M k (G)=C W k (G) [2]. On the other hand, recalling the power-series expansion of the function e x , we have another expression for the Estrada index of G as follows:

EE(G)= k = 0 M k ( G ) k ! = k = 0 C W k ( G ) k ! .
(20)

In particular, if G is a bipartite graph, then by Proposition 6, we get

EE(G)= k = 0 M 2 k ( G ) ( 2 k ) ! = k = 0 C W 2 k ( G ) ( 2 k ) ! .
(21)

We are now ready to give some new upper bounds for EE(G).

Theorem 7 Let G be a graph with n vertices, m edges, t triangles, maximum degree Δ and degree sequence ( d 1 , d 2 ,, d n ). Then

EE(G)< n Δ ( e Δ 1 ) ,
(22)
EE(G)<n+ 2 m Δ 2 ( e Δ 1 Δ ) ,
(23)
EE(G)<n+m+ Z g 1 ( G ) Δ 3 ( e Δ 1 Δ Δ 2 2 ) ,
(24)
EE(G)<n+m+t+ 2 Z g 2 ( G ) Δ 4 ( e Δ 1 Δ Δ 2 2 Δ 3 6 ) ,
(25)
EE(G)< i = 1 n e d i 1 d i .
(26)

Moreover, if G admits an orientation with maximum outdegree dΔ/2, then

EE(G)< n 4 d ( Δ d ) ( e 4 d ( Δ d ) 1 ) .
(27)

Proof We first consider (22). By (20), Theorem 4 and noticing that C W 0 (G)=n, C W 1 (G)=0, C W 2 (G)=2mnΔ, we have

E E ( G ) = C W 0 ( G ) + C W 1 ( G ) + C W 2 ( G ) 2 ! + k = 3 C W k ( G ) k ! < n + n Δ 2 ! + k = 3 n Δ k 1 k ! = n + n Δ ( k = 0 Δ k k ! 1 Δ ) = n Δ ( e Δ 1 ) .

The discussion for (23)-(27) is analogous by observing that C W 2 (G)=2m= i = 1 n d i , C W 3 (G)=6t< W 2 (G)=Z g 1 (G) and, C W 2 (G)= W 1 (G)n 4 d ( Δ d ) with equality if and only if G is a Δ-regular Euler graph. □

For bipartite graphs, from (21) and the power-series expansion of the hyperbolic cosine cosh(x)=( e x + e x )/2, one can easily obtain the following result by a similar reasoning as in the proof of Theorem 7.

Theorem 8 Let G be a bipartite graph with n vertices, m edges, maximum degree Δ and degree sequence ( d 1 , d 2 ,, d n ). Then

EE(G)n+ n Δ ( cosh ( Δ ) 1 ) ,
(28)
EE(G)n+ 2 m Δ 2 ( cosh ( Δ ) 1 ) ,
(29)
EE(G)n+m+ Z g 1 ( G ) Δ 3 ( cosh ( Δ ) 1 Δ 2 2 ) ,
(30)
EE(G)n+m+ 2 Z g 2 ( G ) Δ 4 ( cosh ( Δ ) 1 Δ 2 2 ) ,
(31)
EE(G)n+ i = 1 n cosh ( d i ) 1 d i .
(32)

Each of the equalities holds in (28)-(32) if and only if each component of G is the complete bipartite graph K Δ , Δ . Moreover, if G admits an orientation with maximum outdegree dΔ/2, then

EE(G)n+ n 4 d ( Δ d ) ( cosh ( 4 d ( Δ d ) ) 1 ) ,
(33)

with equality if and only if Δ is even and each component of G is the complete bipartite graph K Δ , Δ .

Similar to Corollary 5, substituting d=1 and d=3 in (33) and (27), respectively, we have the following corollary.

Corollary 9 Let G be a graph of order n with maximum degree Δ. If G is a tree (or forest) and Δ2, then

EE(G)<n+ n 4 ( Δ 1 ) ( cosh ( 4 ( Δ 1 ) ) 1 ) .
(34)

If G is a planar graph and Δ6, then

EE(G)< n 12 ( Δ 3 ) ( e 12 ( Δ 3 ) 1 ) .
(35)

Remark In the past few years, a number of upper bounds on the Estrada index of graphs have been established by using the algebraic techniques (see, for example, [10, 11, 14, 16]). In comparison to the algebraic techniques, the bounds based on our graph-theoretical method are related to the degree parameters (mainly the maximum degree), which are somewhat different from the previous ones. Moreover, our method would be more effective in some cases. For example, in [10] de la Peña et al. showed that, for any graph G,

EE(G)n1+ e 2 m ,

which was later improved by Zhou in [16] as follows:

EE(G)n1 2 m + e 2 m .
(36)

Here, our bound (23) would be better than the bound (36) when 2Δ< 2 m . To see this, we first consider the function f(x)=( e x 1x)/ x 2 with x2, which is strictly increasing with respect to x since f (x)=[(x2) e x +x+2]/ x 3 >0 when x2. Then for 2Δ< 2 m , we get

n+ 2 m Δ 2 ( e Δ 1 Δ ) =n+2mf(Δ)<n+2mf( 2 m )=n1 2 m + e 2 m .

In addition, for a bipartite graph G, the authors in [10] proved that

EE(G)n2+2cosh( m ).
(37)

Here, our bound (29) would be better than the bound (37) when 2Δ< m . Indeed, when x2 the function f(x)=(coshx1)/ x 2 is strictly increasing with respect to x since f (x)=[(x2)( e x e x )+4(1 e x )]/2 x 3 >0. Therefore, for 2Δ< m , we have

n+ 2 m Δ 2 ( cosh ( Δ ) 1 ) =n+2mf(Δ)<n+2mf( m )=n2+2cosh( m ).

References

  1. Gutman I, Trinajstić N: Graph theory and molecular orbitals. Total π -electron energy of alternant hydrocarbons. Chem. Phys. Lett. 1972, 17: 535–538. 10.1016/0009-2614(72)85099-1

    Article  Google Scholar 

  2. Cvetković D, Doob M, Sachs H: Spectra of Graphs-Theory and Application. Academic Press, New York; 1980.

    Google Scholar 

  3. Gutman I: Remark on the moment expansion of total π -electron energy. Theor. Chim. Acta 1992., 83: Article ID 313318

    Google Scholar 

  4. Gutman I, Marković S, Vesović A, Estrada E: Approximating total π -electron energy in terms of spectral moments. A quantitative approach. J. Serb. Chem. Soc. 1998, 63: 639–646.

    Google Scholar 

  5. Randić M: Random walks and their diagnostic value for characterization of atomic environment. J. Comput. Chem. 1980, 1: 386–399. 10.1002/jcc.540010410

    Article  Google Scholar 

  6. Estrada E: Characterization of 3D molecular structure. Chem. Phys. Lett. 2000, 319: 713–718. 10.1016/S0009-2614(00)00158-5

    Article  Google Scholar 

  7. Estrada E, Rodríguez-Valázquez JA, Randić M: Atomic branching in molecules. Int. J. Quant. Chem. 2006, 106: 823–832. 10.1002/qua.20850

    Article  Google Scholar 

  8. Estrada E, Rodríguez-Valázquez JA: Subgraph centrality in complex networks. Phys. Rev. E 2005., 71: Article ID 056103

    Google Scholar 

  9. Das KC, Lee SG: On the Estrada index conjecture. Linear Algebra Appl. 2009, 431: 1351–1359. 10.1016/j.laa.2009.05.007

    Article  MathSciNet  Google Scholar 

  10. de la Peña JA, Gutman I, Rada J: Estimating the Estrada index. Linear Algebra Appl. 2007, 427: 70–76. 10.1016/j.laa.2007.06.020

    Article  MathSciNet  Google Scholar 

  11. Fath-Tabar GH, Ashrafi AR: New upper bounds for Estrada index of bipartite graphs. Linear Algebra Appl. 2011, 435: 2607–2611. 10.1016/j.laa.2011.01.034

    Article  MathSciNet  Google Scholar 

  12. Gutman I, Estrada E, Rodríguez-Valázquez JA: On a graph-spectrum-based structure descriptor. Croat. Chem. Acta 2007, 80: 151–154.

    Google Scholar 

  13. Gutman I: Lower bounds for Estrada index. Publ. Inst. Math. (Belgr.) 2008, 83: 1–7. 10.2298/PIM0897001G

    Article  Google Scholar 

  14. Liu J, Liu B: Bounds of the Estrada index of graphs. Appl. Math. J. Chin. Univ. Ser. B 2010, 25: 325–330. 10.1007/s11766-010-2237-6

    Article  Google Scholar 

  15. Zhao H, Jia Y: On the Estrada index of bipartite graph. MATCH Commun. Math. Comput. Chem. 2009, 61: 495–501.

    MathSciNet  Google Scholar 

  16. Zhou B: On Estrada index. MATCH Commun. Math. Comput. Chem. 2008, 60: 485–492.

    MathSciNet  Google Scholar 

  17. Du Z, Zhou B: The Estrada index of unicyclic graphs. Linear Algebra Appl. 2012, 436: 3149–3159. 10.1016/j.laa.2011.10.020

    Article  MathSciNet  Google Scholar 

  18. Ilic A, Stevanović D: The Estrada index of chemical trees. J. Math. Chem. 2010, 47: 305–314. 10.1007/s10910-009-9570-0

    Article  MathSciNet  Google Scholar 

  19. Zhang J, Zhou B, Li J: On Estrada index of trees. Linear Algebra Appl. 2011, 434: 215–223. 10.1016/j.laa.2010.08.025

    Article  MathSciNet  Google Scholar 

  20. Gutman I, Deng H, Radenković S: The Estrada index: an updated survey. In Selected Topics on Applications of Graph Spectra. Edited by: Cvetković D, Gutman I. Math. Inst., Beograd; 2011:155–174.

    Google Scholar 

  21. Jajcaya R, Malniǎ A, Marušč D: On the number of closed walks in vertex-transitive graphs. Discrete Math. 2007, 307: 484–493. 10.1016/j.disc.2005.09.039

    Article  MathSciNet  Google Scholar 

  22. Shibata Y, Shirahata M, Osawa S: Counting closed walks in generalized de Bruijn graphs. Inf. Process. Lett. 1994, 49: 135–138. 10.1016/0020-0190(94)90090-6

    Article  MathSciNet  Google Scholar 

  23. Fiol MA, Garriga E: Number of walks and degree powers in a graph. Discrete Math. 2009, 309: 2613–2614. 10.1016/j.disc.2008.03.025

    Article  MathSciNet  Google Scholar 

  24. Hayes TP: A simple condition implying rapid mixing of single-site dynamics on spin systems. 47th Ann. IEEE Symp. Found. Comp. Sci. (FOCS’06) 2006, 39–46.

    Google Scholar 

  25. Gonçalves D: Covering planar graphs with forests, one having bounded maximum degree. J. Comb. Theory, Ser. B 2009, 99: 314–322. 10.1016/j.jctb.2008.07.004

    Article  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees for their extremely helpful comments and suggestions towards improving the original version of this paper. The first author was supported partially by the Scientic Research Foundation of Guangxi University (Grant No. XBZ130083) and NNSF of China (No. 11361007). The second author was supported by NNSF of China (No. 10831001).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Jianguo Qian.

Additional information

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors contributed equally and significantly in writing this article. All authors read and approved the final manuscript.

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, X., Qian, J. Bounds on the number of closed walks in a graph and its applications. J Inequal Appl 2014, 199 (2014). https://doi.org/10.1186/1029-242X-2014-199

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1186/1029-242X-2014-199

Keywords