Spanning trees with pairwise nonadjacent endvertices
| Autor: | Böhme, T., Bohme, T., Broersma, Haitze J., Gobel, F., Kostochka, A.V., Stiebitz, M. |
|---|---|
| Přispěvatelé: | Discrete Mathematics and Mathematical Programming |
| Rok vydání: | 1997 |
| Předmět: |
Discrete mathematics
Spanning tree Trémaux tree Spanning tree with pairwise nonadjacent endvertices Tree (graph theory) Depth-first-search tree Simplex graph IR-30145 Theoretical Computer Science Combinatorics Edge-transitive graph Graph power Discrete Mathematics and Combinatorics METIS-140784 Graph factorization Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete mathematics, 170(170), 219-222. Elsevier |
| ISSN: | 0012-365X |
| DOI: | 10.1016/s0012-365x(96)00306-8 |
| Popis: | A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect