✦ LIBER ✦

Some results on covers of complete graphs

✍ Scribed by Rongquan Feng; Jin Ho Kwak

Publisher: Springer
Year: 2000
Tongue: English
Weight: 176 KB
Volume: 45
Category: Article
ISSN: 1001-6538
DOI: 10.1007/bf02887404

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Some results on λ-valuation of graphs in

Some results on λ-valuation of graphs involving complete bipartite graphs

✍ Sze-Chin Shee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 389 KB

Shee, S.-C., Some results on I-valuation of graphs involving complete bipartite graphs, Discrete Mathematics 87 (1991) 73-80. In this paper we show that a graph G obtained from a complete bipartite graph K,,, and a collection of q (cmax{m, n}) stars G, by joining the centre of G, to every vertex of

On 2-Arc-Transitive Covers of Complete G

On 2-Arc-Transitive Covers of Complete Graphs

✍ Shao-fei Du; Dragan Marušič; Adrian O Waller 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 282 KB

Regular covers of complete graphs which are 2-arc-transitive are investigated. A classification is given of all such graphs whose group of covering transformations is either cyclic or isomorphic to Z p \_Z p , where p is a prime and whose fibrepreserving subgroup of automorphisms acts 2-arc-transiti

Antipodal Distance Transitive Covers of

Antipodal Distance Transitive Covers of Complete Graphs

✍ C.D. Godsil; R.A. Liebler; C.E. Praeger 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 352 KB

A distance-transitive antipodal cover of a complete graph K n possesses an automorphism group that acts 2-transitively on the fibres. The classification of finite simple groups implies a classification of finite 2-transitive permutation groups, and this allows us to determine all possibilities for s

Some APX-completeness results for cubic

Some APX-completeness results for cubic graphs

✍ Paola Alimonti; Viggo Kann 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 122 KB

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded

Antipodal Distance-transitive Covers of

Antipodal Distance-transitive Covers of Complete Bipartite Graphs

✍ A.A. Ivanov; Robert A. Liebler; Tim Penttila; Cheryl E. Praeger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 480 KB

This paper completes the classification of antipodal distance-transitive covers of the complete bipartite graphs K k , k , where k у 3 . For such a cover the antipodal blocks must have size r р k . Although the case r ϭ k has already been considered , we give a unified treatment of r р k . We use d

On covers of graphs

✍ Maxová Jaroslav; Jana Nešetřil 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We concentrate on two problems from the area of coverings of graphs, on an oriented version of Perfect Path Double Cover (PPDC) and on oriented version of Weighted Cycle Cover.