✦ LIBER ✦

Niche graphs and mixed pair graphs of tournaments

✍ Scribed by Bowser, Steve; Cable, Charles; Lundgren, Richard

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 339 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199908)31:4<319::aid-jgt7>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

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 order, a path of even order, a forest of odd order consisting of two paths, a forest of even order consisting of three paths, or a forest of four or more paths. (In this description, we consider an isolated vertex to be a path.

📜 SIMILAR VOLUMES

The domination and competition graphs of

The domination and competition graphs of a tournament

✍ Fisher, David C.; Lundgren, J. Richard; Merz, Sarah K.; Reid, K. B. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB 👁 1 views

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 cater

Simultaneous intersection representation

Simultaneous intersection representation of pairs of graphs

✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 1 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons

Graphs omitting sums of complete graphs

✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 1 views

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m • K n )-free graphs such that every countable (m • K n )-free graph occurs as an induced subgraph of one of the graphs G i .

Simple Markov-chain algorithms for gener

Simple Markov-chain algorithms for generating bipartite graphs and tournaments

✍ Ravi Kannan; Prasad Tetali; Santosh Vempala 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 1 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g

Embedding of graphs in two-irregular gra

Embedding of graphs in two-irregular graphs

✍ M. Axenovich; Z. Füredi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 1 views

Cyclicity of graphs

✍ Hammack, Richard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 1 views

The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including c