Do nearly balanced multigraphs have more spanning trees?
✍ Scribed by Ching-Shui Cheng; Joseph C. Masaro; Chi Song Wong
- Publisher
- John Wiley and Sons
- Year
- 1985
- Tongue
- English
- Weight
- 320 KB
- Volume
- 9
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
We prove that, with very few exceptions, every graph of order n, n = 0, 1 (mod 4) and size a t most n -1, is contained in a self-complementary graph of order n. We study a similar problem for digraphs.
Throughout the paper, G and D will denote a finite graph and a finite digraph, respectively, without loops or multiple edges, with vertex-sets V ( G ) and V ( D ) , and edge-sets E(G) and E(D); define r ( G ) = IE(G)I, e(D) = (E(D)I. An edge of G joining x and y is denoted by xy, an edge of D from i to t by ( z , t ) , and a symmetric edge of D joining u and u by uu. Cj denotes a cycle of G of length i z= 3. G U H will refer to two vertex disjoint graphs G and H , and mG to m disjoint copies of G. If
G is said to be a self-complementary graph (or S.C. graph) if it is isomorphic to its complement c, then, there exists a permutation (T of V(G), called S.C. permutation of G, such that xy is an edge of G if and only if a ( x ) u ( y ) is an edge of (for simplicity, we use the notation ( ~( x y ) = u(x)cr(y)). We say that G is contained in a graph G' if there exists a subgraph in G' isomorphic to G. The same is applicable to D .
It is known [6,7,8] that if G is an S.C. graph of order n , then n = 0, 1 (mod 4), and its S.C. permutation has all its cycles of lengths being multiples of 4 (except one of length one if n is odd), and lengths of cycles of an S.C. permutation of an S . C . digraph D are even (except one of length one if the order of D is odd). Furthermore, if G is an S.C.