Results 11 to 20 of about 42,490 (162)
On Polynomials of Spanning Trees [PDF]
Annals of Combinatorics, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Chung, Fan, Yang, Chao
openaire +1 more source
End‐faithful spanning trees in graphs without normal spanning trees [PDF]
Journal of Graph Theory, 2022 AbstractSchmidt characterised the class of rayless graphs by an ordinal rank function, which makes it possible to prove statements about rayless graphs by transfinite induction. Halin asked whether Schmidt's rank function can be generalised to characterise other important classes of graphs. In this paper, we address Halin's question: we characterise an
Carl Bürger, Jan Kurkofka
openaire +3 more sources
Spanning trees with small diameters
AKCE International Journal of Graphs and Combinatorics, 2020 A spanning tree with small diameter of a graph has many applications. In this paper we first make the following conjecture and show that the condition is best possible if it is true. If a connected graph satisfies , then has a spanning tree with diameter
Mikio Kano, Hajime Matsumura
doaj +1 more source
Constructing Independent Spanning Trees on Transposition Networks
IEEE Access, 2020 In interconnection networks, data distribution and fault tolerance are crucial services. This study proposes an effective algorithm for improving connections between networks.
Chien-Fu Lin +2 more
doaj +1 more source
Spanning Trees Minimizing Branching Costs [PDF]
Discrete Mathematics & Theoretical Computer ScienceThe Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$.
Luisa Gargano, Adele A. Rescigno
doaj +1 more source
Graph node rank based important keyword detection from Twitter [PDF]
Applied Computing and Informatics, 2021 Social media networks like Twitter, Facebook, WhatsApp etc. are most commonly used medium for sharing news, opinions and to stay in touch with peers. Messages on twitter are limited to 140 characters.
Mukesh Kumar, Palak Rehan
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 Longest Spanning Tree with Neighborhoods [PDF]
Discrete Mathematics, Algorithms and Applications, 2018 We study a maximization problem for geometric network design. Given a set of [Formula: see text] compact neighborhoods in [Formula: see text], select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here, we give an approximation algorithm with ratio [Formula: see text], which represents
Ke Chen 0011, Adrian Dumitrescu
openaire +2 more sources
Completely Independent Spanning Trees in (Partial) k-Trees
Discussiones Mathematicae Graph Theory, 2015 Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint.
Matsushita Masayoshi +2 more
doaj +1 more source