Results 1 to 10 of about 42,726 (118)
On the Number of Spanning Trees of Graphs [PDF]
The Scientific World Journal, 2014 We establish some bounds for the number of spanning trees of connected graphs in terms of the number of vertices (n), the number of edges (m), maximum vertex degree (Δ1), minimum vertex degree (δ), first Zagreb index (M1), and Randić index (R-1).
Ş. Burcu Bozkurt, Durmuş Bozkurt
doaj +2 more sources
Spanning trees with a bounded number of leaves [PDF]
Opuscula Mathematica, 2017 In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph \(G\) with \(n\geq 3\) vertices, if \(d(u)+d(v)\geq n-k+1\) for all non-adjacent vertices \(u\) and \(v\) of \(G\) (\(k\geq 1\)), then \(G\) has a spanning tree with at most \(k ...
Junqing Cai +3 more
doaj +1 more source
On relation between the Kirchhoff index and number of spanning trees of graph [PDF]
Communications in Combinatorics and Optimization, 2020 Let $G$ be a simple connected graph with degree sequence $(d_1,d_2,\ldots, d_n)$ where $\Delta =d_1\geq d_2\geq\cdots\geq d_n=\delta >0$ and let $\mu_1\geq \mu_2\geq\cdots\geq\mu_{n-1}>\mu_n=0$ be the Laplacian eigenvalues of $G$.
Igor Milovanovic +3 more
doaj +1 more source
Complexity trees of the sequence of some nonahedral graphs generated by triangle
Heliyon, 2020 Calculating the number of spanning trees of a graph is one of the widely studied graph problems since the Pioneer Gustav Kirchhoff (1847). In this work, using knowledge of difference equations we drive the explicit formulas for the number of spanning ...
S.N. Daoud, Wedad Saleh
doaj +1 more source
On the Minimum Number of Spanning Trees in Cubic Multigraphs
Discussiones Mathematicae Graph Theory, 2020 Let G2n, H2n be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G2n), t (H2n) denote the number of spanning trees in G2n, H2n, respectively. We prove that for n ≥ 3 there is the unique G2n
Bogdanowicz Zbigniew R.
doaj +1 more source
Axioms, 2022 Let Pn be a pentagonal chain with 2n pentagons in which two pentagons with two edges in common can be regarded as adding one vertex and two edges to a hexagon.
Yue Tu +3 more
doaj +1 more source
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Discussiones Mathematicae Graph Theory, 2013 Let G1 and G2 be simple graphs and let n1 = |V (G1)|, m1 = |E(G1)|, n2 = |V (G2)| and m2 = |E(G2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1 □G2 of G1 and G2. We show that: and .
Azarija Jernej
doaj +1 more source
On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs [PDF]
Transactions on Combinatorics, 2022 In this paper, we delve into studying some relations between the structure of the cycles and spanning trees of a graph through the lens of its cycle and spanning tree hypergraphs which are hypergraphs with the edge set of the graph as their vertices ...
Alireza Mofidi
doaj +1 more source
BUILDING MINIMUM SPANNING TREES BY LIMITED NUMBER OF NODES OVER TRIANGULATED SET OF INITIAL NODES
Information and Telecommunication Sciences, 2023 Background. The common purpose of modelling and using minimum spanning trees is to ensure efficient coverage. In many tasks of designing efficient telecommunication networks, the number of network nodes is usually limited. In terms of rational allocation,
Вадим Романюк
doaj +1 more source
Complexity of Join and Corona graphs and Chebyshev polynomials
Journal of Taibah University for Science, 2018 Boesh and Prodinger have shown how to use properties of Chebyshev polynomials to compute formulas for the number of spanning trees of some special graphs.
S. N. Daoud
doaj +1 more source