✦ LIBER ✦

The connectivity of acyclic orientation graphs

✍ Scribed by Carla D. Savage; Cun-Quan Zhang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 362 KB
Volume: 184
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00201-x

No coin nor oath required. For personal study only.

✦ Synopsis

The acyclic orientation graph, AO(G), of an undirected graph, G, is the graph whose vertices are the acyclic orientations of G and whose edges are the pairs of orientations differing only by the reversal of one edge. Edelman (1984) has observed that it follows from results on polytopes that when G is simple, the connectivity of AO(G) is at least n -c, where n is the number of vertices and c is the number of components of G. In this paper we give a simple graph-theoretic proof of this fact. Our proof uses a result of independent interest. We establish that if H is a triangle-free graph with minimum degree at least k, and the graph obtained by contracting the edges of a matching in H is k-connected, then H is k-connected.

The connectivity bound on AO(G) is tight for various graphs including Kn, Kp, q, and trees. Applications and extensions are discussed, as well as the connection with polytopes. (~) 1998 Elsevier Science B.V. All rights reserved

📜 SIMILAR VOLUMES

Acyclic orientations of graphs

✍ Richard P. Stanley 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 708 KB

## Let G be a finite graph with p vertices and x its chromatic polynomial. A combinatorial interpretation is given to the positive integer (-l)px(-A), where h is a positive integer, in terms of acyclic orientations of G. In particular, (-l)Px(-1) is the number of acyclic orientations of G. An appl

Acyclic Orientations of Random Graphs

✍ C.M Reidys 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 195 KB

An acyclic orientation of an undirected graph is an orientation of its edges such that the resulting directed graph contains no cycles. The random graph G is a n, p probability space consisting of subgraphs of K that are obtained by selecting each n K -edge with independent probability p. The random

Generating the Acyclic Orientations of a

Generating the Acyclic Orientations of a Graph

✍ Matthew B Squire 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 206 KB

The acyclic orientations of a graph are related to its chromatic polynomial, to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to Ž . require O n time per acyclic orientation ge

Sinks in Acyclic Orientations of Graphs

✍ David D. Gebhard; Bruce E. Sagan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 183 KB

Greene and Zaslavsky proved that the number of acyclic orientations of a graph G with a unique sink at a given vertex is, up to sign, the linear coefficient of the chromatic polynomial. We give three proofs of this result using pure induction, noncommutative symmetric functions, and an algorithmic b

Acyclic orientations of complete biparti

Acyclic orientations of complete bipartite graphs

✍ Douglas B. West 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 216 KB

For a complete bipartite graph, the number of dependent edges in an acyclic orientation can be any integer from n-1 to e, where n and e are the number of vertices and edges in the graph. ## Ke3,words: Bipartite graph; Acyclic orientation Ill combinatorics we often ask whether an integer parameter

Searching for acyclic orientations of gr

Searching for acyclic orientations of graphs

✍ Martin Aigner; Eberhard Triesch; Zsolt Tuza 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 397 KB

We want to find an unknown acyclic orientation ~\* of an (undirected) graph G by testing for certain edges how they are oriented according to ~\*. How many tests do we need in the worst case? We give upper and lower bounds for this number c(G) in terms of the independence number of G and study the c