✦ LIBER ✦

The Number of Dependent Arcs in an Acyclic Orientation

✍ Scribed by David C. Fisher; Kathryn Fraughnaugh; Larry Langley; Douglas B. West

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 207 KB
Volume: 71
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1769

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph with n nodes, e edges, chromatic number /, and girth g. In an acyclic orientation of G, an arc is dependent if its reversal creates a cycle. It is well known that if /<g, then G has an acyclic orientation without dependent arcs. Edelman showed that if G is connected, then every acyclic orientation has at most e&n+1 dependent arcs. We show that if G is connected and /<g, then G has an acyclic orientation with exactly d dependent arcs for all d e&n+1. We also give bounds on the minimum number of dependent arcs in graphs with / g. 1997 Academic Press Corollary 2. If G is a graph with k components, then d max (G )= e(G)&n(G )+k.

📜 SIMILAR VOLUMES

The Geodetic Number of an Oriented Graph

✍ Gary Chartrand; Ping Zhang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 149 KB

For two vertices u and v of an oriented graph D, the set I (u, v) consists of all vertices lying on a uv geodesic or vu geodesic in D. If S is a set of vertices of D, then I (S) is the union of all sets I (u, v) for vertices u and v in S. The geodetic number g(D) is the minimum cardinality among the

The number of pancyclic arcs in a k-stro

The number of pancyclic arcs in a k-strong tournament

✍ Anders Yeo 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 2 views

## Abstract A __tournament__ is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is __pancyclic__ in a digraph __D__, if it belongs to a cycle of length __l__, for all 3 ≤ __l__ ≤ |__V__ (__D__) |. Let __p__(__D__) denote the number of pancyclic arcs in a

The number of rooted maps on an orientab

The number of rooted maps on an orientable surface

✍ Edward A Bender; E.Rodney Canfield 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 290 KB

Types of superregular matrices and the n

Types of superregular matrices and the number of n-arcs and complete n-arcs in PG (r, q)

✍ Gerzson Kéri 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract Based on the classification of superregular matrices, the numbers of non‐equivalent __n__‐arcs and complete __n__‐arcs in PG(__r__, __q__) are determined (i) for 4 ≤ __q__ ≤ 19, 2 ≤ __r__ ≤ q − 2 and arbitrary __n__, (ii) for 23 ≤ __q__ ≤ 32, __r__ = 2 and __n__ ≥ q − 8<$>. The equivale

Orientation dependence of the Landé fact

Orientation dependence of the Landé factor in an inversion layer

✍ M. Kornexl 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 295 KB

The magneto-optical properties of a biased semiconductor inversion layer (GaAlAs-GaAs) are calculated for applied magnetic fields in the Faraday and Voigt configurations. Electric and magnetic dipole transitions for spin flip in an n-type inversion layer are investigated. Resulting line shapes and t

Time dependence of nonequilibrium in the

Time dependence of nonequilibrium in the Hg resonance level in an AC arc plasma

✍ D. Karabourniotis; S. Couris 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 345 KB