On the number of spanning trees in directed circulant graphs. (English) Zbl 0974.05043

Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M.

Networks 37, No. 3, 129-133 (2001).

Summary: Let \(g_k(n)\) [respectively, \(f_k(n)\)] be the maximum number of spanning trees in directed circulant graphs (respectively, regular directed graphs) with \(n\) vertices and out-degrees equal to \(k>1\). We show that \(g_k(n)= k^{n(1+ o(1))}\) and \(f_k(n)= k^{n(1+ o(1))}\). Moreover, we prove that \(g_2(n)= \lfloor (2^n+ 1)/3\rfloor\).

MSC:

05C30	Enumeration in graph theory
05C05	Trees
94C15	Applications of graph theory to circuits and networks

Keywords:

network reliability; spanning trees; directed circulant graphs

References:

[1]	Baron, Fibonacci Q 23 pp 258– (1985)
[2]	Boesch, Graphs Combin 2 pp 191– (1986) · Zbl 0651.05028
[3]	Boesch, SIAM J Alg Discr Methods 7 pp 89– (1986) · Zbl 0578.05046
[4]	and Spectra of graphs, VEB Deutscher Verlag der Wissenschafen, Berlin, 1982.
[5]	Lonc, Networks 30 pp 47– (1997) · Zbl 0882.05073
[6]	McKay, Eur J Combin 4 pp 149– (1983) · Zbl 0517.05043
[7]	and Designing of regular graphs with the use of evolutionary computation, Proc Congress on Evolutionary Computation, Washington, DC, 1999, pp. 1550-1556.
[8]	Sedla?ek, Casop Pest Mat 91 pp 221– (1966)
[9]	Sedla?ek, Casop Pest Mat 94 pp 217– (1969)
[10]	Wojciechowski, J Franklin Inst 326 pp 889– (1989) · Zbl 0723.05071