✦ LIBER ✦

Interval competition graphs of symmetric diagraphs

✍ Scribed by J.Richard Lundgren; Craig W. Rasmussen; John S. Maybee

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 700 KB
Volume: 119
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90121-9

No coin nor oath required. For personal study only.

✦ Synopsis

interval competition graphics of symmetric digrapha. Discrete Mathematics I I9 (1993) I I3 122. The competition graph of a loopless symmetric digraph If is the rwo-.\rc'p grclph. S,(H). Necessary and sufficient conditions on If are given for S,(ff) to be interval or unit interval. These are useful properties when application requires that the competition graph be efficiently colorable. Computational aspects are discussed. as are related open problems. In this paper we answer the following question: given a loopless symmetric digraph D with underlying interval graph H. what conditions are necessary and sufficient for the competition graph of D to be interval or unit interval'? This question, first posed by Raychaudhuri and Roberts [lo]. was left open in our previous paper 171. In that paper we presented the background of this question in the context of the channel assignment problem as well as recent results on several questions posed by Raychaudhuri and Roberts [IS, IO]. Here we extend those results. We begin by stating definitions, and results from our previous work, that will be useful here. Proofs will be omitted; the interested reader may consult 171. Suppose that D = ( V, A ) is a digraph and B and C are (not necessarily disjoint) sets of vertices in D. The ~~erzrrulizrd competition graph G(D, B, C) corresponding to D, B,

📜 SIMILAR VOLUMES

Interval digraphs: An analogue of interv

Interval digraphs: An analogue of interval graphs

✍ S. Das; M. Sen; A. B. Roy; D. B. West 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 728 KB

Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uu in the intersection digraph when the "source set" of u intersects the "terminal set" of u. Every n-vertex digraph is an intersection digraph of o

An evolution of interval graphs

✍ Edward R. Scheinerman 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 985 KB

Interval representations of planar graph

Interval representations of planar graphs

✍ Carsten Thomassen 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 867 KB

Chromatic numbers of competition graphs

✍ J.Richard Lundgren; Sarah K. Merz; Craig W. Rasmussen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 964 KB

N-extendability of symmetric graphs

✍ R. E. L. Aldred; D. A. Holton; Dingjun Lou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

## Abstract It is proved that a cyclically (__k__ − 1)(2__n__ − 1)‐edge‐connected edge transitive __k__‐regular graph with even order is __n__‐extendable, where __k__ ≥ 3 and __k__ − 1 ≥ __n__ ≥ ⌈(__k__ + 1)/2⌉. The bound of cyclic edge connectivity is sharp when __k__ = 3. © 1993 John Wiley & Sons

Vertex-transitive graphs: Symmetric grap

Vertex-transitive graphs: Symmetric graphs of prime valency

✍ Peter Lorimer 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 642 KB

Let G be a group acting symmetrically on a graph 2, let G, be a subgroup of G minimal among those that act symmetrically on 8, and let G2 be a subgroup of G, maximal among those normal subgroups of GI which contain no member except 1 which fixes a vertex of Z. The most precise result of this paper i