Premium
Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
Author(s) -
Jackson Bill
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120314
Subject(s) - digraph , combinatorics , mathematics , vertex (graph theory) , eulerian path , arc (geometry) , undirected graph , strongly connected component , graph , directed graph , feedback arc set , discrete mathematics , line graph , voltage graph , geometry , pure mathematics , lagrangian
We apply proof techniques developed by L. Lovász and A. Frank to obtain several results on the arc‐connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditions. The final result is concerned with orienting the edges of a mixed graph (consisting of vertices, undirected edges, and directed arcs) in such a way that the resulting digraph is as arc‐connected as possible.