Domination in partitioned graphs

• Autorzy: Zsolt Tuza , Preben Dahl Vestergaard
• Języki publikacji: EN

Abstrakty

EN

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).

Słowa kluczowe

EN

graph; dominating set; domination number; vertex partition

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C35: Extremal problems
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2002
• Tom: 22
• Numer: 1
• Strony: 199-210

Daty

wydano

2002

otrzymano

2000-11-10

poprawiono

2001-05-09

Twórcy

autor

Zsolt Tuza

• Computer and Automation Institute, Hungarian Academy of Sciences, Budapest
• Department of Computer Science, University of Veszprém, Hungary

autor

Preben Dahl Vestergaard

• Department of Mathematics, Aalborg University, Fredrik Bajers Vej 7E, DK-9220, Aalborg Ø, Denmark

Bibliografia

• [1] B.L. Hartnell and P.D. Vestergaard, Partitions and dominations in a graph, Manuscript, pp. 1-10.
• [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., New York, N.Y., 1998).
• [3] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.
• [4] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277-295, doi: 10.1017/S0963548300002042.
• [5] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congressus Numerantium 132 (1998) 85-91.

Identyfikatory

DOI

10.7151/dmgt.1169