✦ LIBER ✦

The domination and competition graphs of a tournament

✍ Scribed by Fisher, David C.; Lundgren, J. Richard; Merz, Sarah K.; Reid, K. B.

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 230 KB
Volume: 29
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199810)29:2<103::aid-jgt6>3.0.co;2-v

No coin nor oath required. For personal study only.

✦ Synopsis

Vertices x and y dominate a tournament T if for all vertices z / = x, y, either x beats z or y beats z. Let dom(T ) be the graph on the vertices of T with edges between pairs of vertices that dominate T . We show that dom(T ) is either an odd cycle with possible pendant vertices or a forest of caterpillars. While this is not a characterization, it does lead to considerable information about dom(T ). Since dom(T ) is the complement of the competition graph of the tournament formed by reversing the arcs of T , complementary results are obtained for the competition graph of a tournament.

📜 SIMILAR VOLUMES

Niche graphs and mixed pair graphs of to

Niche graphs and mixed pair graphs of tournaments

✍ Bowser, Steve; Cable, Charles; Lundgren, Richard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB 👁 2 views

In our efforts to study the niche graph of a tournament T , we have found it easier to study the complement, which we call the ''mixed pair'' graph of T and denote MP (T ). We show that an undirected graph G is MP (T ), for some tournament T , if and only if G is one of the following: a cycle of odd

Graphs with large total domination numbe

Graphs with large total domination number

✍ Michael A. Henning 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

Degree sequences of graphs and dominance

Degree sequences of graphs and dominance order

✍ Triesch, Eberhard 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB 👁 2 views

Suppose that the graphical partition H(A) = (a: 2 . . . 2 a:) arises from A = (al 2 . . . 2 a,) by deleting the largest summand a1 from A and reducing the a1 largest of the remaining summands by one. Let (a;+l 2 . . 2 ah) = H ( A ) denote the partition obtained by applying the operator H i times. We

A semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 1 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 2 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas

The ratio of the irredundance number and

The ratio of the irredundance number and the domination number for block-cactus graphs

✍ Zverovich, V. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that γ(G) < 2ir(G) for