Spaces of Domino Tilings.
Spaces related to gamma-sets
Spanning caterpillars with bounded diameter
A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most (at most n).
Spanning subgraphs of embedded graphs
Spanning tree congestion of rook's graphs
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 and function classes.
Spanning trees of bounded degree.
Spanning trees of infinite graphs
Spanning trees of locally finite graphs
Spanning trees whose reducible stems have a few branch vertices
Let be a tree. Then a vertex of with degree one is a leaf of and a vertex of degree at least three is a branch vertex of . The set of leaves of is denoted by and the set of branch vertices of is denoted by . For two distinct vertices , of , let denote the unique path in connecting and Let be a tree with . For each leaf of , let denote the nearest branch vertex to . We delete from for all . The resulting subtree of is called the reducible stem of and denoted...
Spanning Trees whose Stems have a Bounded Number of Branch Vertices
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 leaves bounded by independence number.
Spanning trees with many leaves and average distance.
Spanning trees with many or few colors in edge-colored graphs
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.
Sparse graphs usually have exponentially many optimal colorings.
Spatial graphs, knots and the cyclic polytope.
Specht modules for finite groups
Specht modules for Weyl groups.
Special Embeddings of the Complete Graph.
Special m-hyperidentities in biregular leftmost graph varieties of type (2,0)
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 satisfies s ≈ t. A class of graph algebras V is called a graph variety if where Σ is a subset of T(X) × T(X). A graph variety 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...