✦ LIBER ✦

On edge transitivity of directed graphs

✍ Scribed by Jayme L. Szwarcfiter

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 476 KB
Volume: 141
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0182-4

No coin nor oath required. For personal study only.

✦ Synopsis

We examine edge transitivity of directed graphs. The class of local comparability graphs is defined as the underlying graphs of locally edge transitive digraphs. The latter generalize edge transitive orientations, while local comparability graphs include comparability, anticomparability, and circle graphs. Recognizing local comparability graphs is NP-complete, however, they are differences of comparability graphs. The concept of dimension is defined so as to generalize that of an edge transitive digraph. Connected proper interval graphs are characterized as exactly the class of local comparability graphs of dimension one. Finally, a new characterization of circle graphs is given also in terms of edge transitivity.

📜 SIMILAR VOLUMES

Edge-transitive planar graphs

✍ Branko Grünbaum; G. C. Shephard 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 590 KB

Remarks on Path-transitivity in Finite G

Remarks on Path-transitivity in Finite Graphs

✍ Marston D.E. Conder; Cheryl E. Praeger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 244 KB

Edge-disjoint cycles in regular directed

Edge-disjoint cycles in regular directed graphs

✍ Alon, Noga; McDiarmid, Colin; Molloy, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB 👁 3 views

We prove that any k-regular directed graph with no parallel edges contains a collection of at least fl(k2) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least ( lCi1 ) disjoint cycles, and note that this holds for k 5 3. o 1996

Edge Weight Reduction Problems in Direct

Edge Weight Reduction Problems in Directed Acyclic Graphs

✍ Susanne E. Hambrusch; Hung-Yi Tu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 378 KB

Let G be a weighted directed acyclic graph in which edge weights are not static quantities, but can be reduced for a certain cost. In this paper we consider the problem of determining which edges to reduce so that the length of the longest paths is minimized and the total cost associated with the re

Classification of edge-transitive rose w

Classification of edge-transitive rose window graphs

✍ István Kovács; Klavdija Kutnar; Dragan Marušič 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

## Abstract Given natural numbers __n__⩾3 and 1⩽__a__, __r__⩽__n__−1, the __rose window graph R__~__n__~(__a, r__) is a quartic graph with vertex set \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\{{{x}}\_{

Graphs on which a dihedral group acts ed

Graphs on which a dihedral group acts edge-transitively

✍ Robin Sue Sanders 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 528 KB

In the present paper we find all the graphs on which a dihedral group acts edge-transitively. First we explicitly build the permissible permutation representations of the dihedral group. Then we use this knowledge to find all the graphs on which a dihedral group acts edge-transitively. These graph