All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 13 Next

Displaying 241 – 260 of 399

Showing per page

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Spanning trees of bounded degree.

Czygrinow, Andrzej, Fan, Genghua, Hurlbert, Glenn, Kierstead, H.A., Trotter, William T. (2001)

The Electronic Journal of Combinatorics [electronic only]

Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha, Dang Dinh Hanh, Nguyen Thanh Loan, Ngoc Diep Pham (2021)

Czechoslovak Mathematical Journal

Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T . The set of leaves of T is denoted by L ( T ) and the set of branch vertices of T is denoted by B ( T ) . For two distinct vertices u , v of T , let P T [ u , v ] denote the unique path in T connecting u and v . Let T be a tree with B ( T ) ≠ ∅ . For each leaf x of T , let y x denote the nearest branch vertex to x . We delete V ( P T [ x , y x ] ) ∖ { y x } from T for all x ∈ L ( T ) . The resulting subtree of T is called the reducible stem of T and denoted...

Spanning Trees whose Stems have a Bounded Number of Branch Vertices

Zheng Yan (2016)

Discussiones Mathematicae Graph Theory

Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma, Xueliang Li (1997)

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.

Special m-hyperidentities in biregular leftmost graph varieties of type (2,0)

Apinant Anantpinitwatna, Tiang Poomsa-ard (2009)

Discussiones Mathematicae - General Algebra and Applications

Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type (2,0). We say that a graph G satisfies a term equation s ≈ t if the corresponding graph algebra A ( G ) ̲ satisfies s ≈ t. A class of graph algebras V is called a graph variety if V = M o d g Σ where Σ is a subset of T(X) × T(X). A graph variety V ' = M o d g Σ ' is called a biregular leftmost graph variety if Σ’ is a set of biregular leftmost term equations. A term equation s ≈ t is called an identity in a variety...

Currently displaying 241 – 260 of 399