✦ LIBER ✦

Edge domination in complete partite graphs

✍ Scribed by Bor-Liang Chen; Hung-Lin Fu

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 416 KB
Volume: 132
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90229-1

No coin nor oath required. For personal study only.

✦ Synopsis

An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D. An edge domatic partition of a graph C=(V, E) is a collection of pairwise-disjoint edge dominating sets of G whose union is E. The maximum size of an edge domatic partition of G is called the edge domatic number. In this paper, we study the edge domatic number of the complete partite graphs and give the answers for balanced complete partite graphs and complete split graphs.

📜 SIMILAR VOLUMES

Edge-connectivity in p-partite graphs

✍ Lutz Volkmann 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

Let G = (V, €1 be a finite, simple p-partite graph with minimum degree 6 and edge-connectivity A. It is proved that if IVI d (2pS)/(p -1) -2 or in special cases that if IVI I ( 2 p 6 ) / ( p -1) -1, then A = S . It is further shown that this result is best possible.

Domination in colored complete graphs

✍ P. Erdös; R. Faudree; A. Gyárfás; R. H. Schelp 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

Efficient edge domination problems in gr

Efficient edge domination problems in graphs

✍ Dana L. Grinstead; Peter J. Slater; Naveed A. Sherwani; Nancy D. Holmes 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 558 KB

Local edge domination critical graphs

✍ Michael A. Henning; Ortrud R. Oellermann; Henda C. Swart 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 521 KB

Sumner and Blitch defined a graph G to be k-y-critical if 7(G) = k and 7(G + uv) = k -1 for each pair u, v of nonadjacent vertices of G. We define a graph to be k-( 7,d)-critical if 7(G) = k and 7(G + uv) = k -I for each pair u, v of nonadjacent vertices of G that are at distance at most d apart. Th

Complete Multi-partite Cutsets in Minima

Complete Multi-partite Cutsets in Minimal Imperfect Graphs

✍ G. Cornuejols; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 316 KB

We show that a minimal imperfect graph \(G\) cannot contain a cutset \(C\) which induces a complete multi-partite graph unless \(C\) is a stable set and \(G\) is an odd hole. This generalizes a result of Tucker, who proved that the only minimal imperfect graphs containing stable cutsets are the odd

Two characterizations of interchange gra

Two characterizations of interchange graphs of complete m-partite graphs

✍ Curtis R. Cook 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 564 KB

A graph G is m-partite if its points can be partitioned into m subsets Yl, . . . . Vm such that every line joins a point in Vi with a point in Vi, i + j. A complete m-partite graph contains every line joining Vi with V-. A complete graph Kp has every pair of its p points adjacent. The nth interchang