✦ LIBER ✦

On arc-traceable tournaments

✍ Scribed by Arthur H. Busch; Michael S. Jacobson; K. B. Reid

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 129 KB
Volume: 53
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20173

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A digraph D = (V, A) is arc‐traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, that is, a hamiltonian path. Given a tournament T, it is well known that it contains a directed hamiltonian path. In this article, we develop the structure necessary for a tournament T to contain an arc xy that is not on any hamiltonian path. Using this structure, we give sufficient conditions for a tournament to be arc‐traceable. In addition, we give examples to show that these conditions are best possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 157–166, 2006

📜 SIMILAR VOLUMES

Weakening arcs in tournaments

✍ Denis Hanson; John W. Moon 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract A weakening arc of an irreducible tournament is an arc whose reversal creates a reducible tournament. We consider properties of such arcs and derive recurrence relations for enumerating strong tournaments with no such arcs, one or more such arcs, and exactly one such arc. We also give s

A problem on arcs without bypasses in to

A problem on arcs without bypasses in tournaments

✍ J.W Moon 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 223 KB

Pancyclic arcs and connectivity in tourn

Pancyclic arcs and connectivity in tournaments

✍ F. Havet 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 226 KB

## Abstract A __tournament__ is an orientation of the edges of a complete graph. An arc is __pancyclic__ in a tournament __T__ if it is contained in a cycle of length __l__, for every 3 ≤ __l__ ≤ |T|. Let __p__(__T__) denote the number of pancyclic arcs in a tournament __T__. In 4, Moon showed that

Spanning k-arc-strong subdigraphs with f

Spanning k-arc-strong subdigraphs with few arcs in k-arc-strong tournaments

✍ Jørgen Bang-Jensen; Jing Huang; Anders Yeo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract Given a __k__‐arc‐strong tournament __T__, we estimate the minimum number of arcs possible in a __k__‐arc‐strong spanning subdigraph of __T__. We give a construction which shows that for each __k__ ≥ 2, there are tournaments __T__ on __n__ vertices such that every __k__‐arc‐strong spann

On strongly jump traceable reals

✍ Keng Meng Ng 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 504 KB

Complementary cycles containing a fixed

Complementary cycles containing a fixed arc in diregular bipartite tournaments

✍ Ke Min Zhang; Yannis Manoussakis; Zeng Min Song 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Let (x, y) be a specified arc in a k-regular bipartite tournament B. We prove that there exists a cycle C of length four through (x, y) in B such that B-C is hamiltonian.