Good acyclic orientations of 4‐regular 4‐connected graphs

DOI10.1002/JGT.22803MaRDI QIDQ6081883zbMATH OpenOpenAlexFDO

Authors Jørgen Bang-Jensen, Matthias Kriesell

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.04569

zbMATH Keywords

2T-graph4-regular graph\(st\)-orderingacyclic orientationsedge-disjoint spanning treesgeneric circuitin-branchingout-branchingpolynomial algorithm

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We study graphs which admit an acyclic orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called {�f good}). A {�f 2T-graph} is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. Clearly a graph has a good orientation if and only if it contains a spanning 2T-graph with a good orientation, implying that 2T-graphs play a central role. Vertex-minimal 2T-graphs with at least two vertices, also known as {�f generic circuits}, play an important role in rigidity theory for graphs. It was shown in cite{bangGOpaper} that every generic circuit has a good orientation. Using this, several results on good orientations of 2T-graphs were obtained in cite{bangGOpaper}. It is an open problem whether there exist a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. In cite{bangGOpaper} complex constructions of 2T-graphs with no good orientation were given, indicating that the problem might be very difficult. In this paper we focus on so-called {�f quartics} which are 2T-graphs where every vertex has degree 3 or 4. We identify a sufficient condition for a quartic to have a good orientation, give a polynomial algorithm to recognize quartics satisfying the condition and a polynomial algorithm to produce such an orientation when this condition is met. As a consequence of these results we prove that every 4-regular and 4-connected graph has a good orientation. iffalse We also provide evidence that even for quartics it may be difficult to find a characterization of those instances which have a good orientation.fi We also show that every graph on $ngeq8$ vertices and of minimum degree at least $lfloorn/2floor$ has a good orientation. Finally we pose a number of open problems.

Recommendations

• Good orientations of unions of edge‐disjoint spanning trees
• Strongly 2-connected orientations of graphs
• On topological aspects of orientations
• An orientation theorem for graphs
• Two‐connected orientations of Eulerian graphs

Cites work

• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Algorithms for plane representations of acyclic digraphs
• Balanced vertex-orderings of graphs
• Computing an st-numbering
• Decomposition of Finite Graphs Into Forests
• Digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Good orientations of unions of edge‐disjoint spanning trees
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• On two minimax theorems in graph
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions
• Small degree out‐branchings

Cited in

(3)

• Good orientations of unions of edge‐disjoint spanning trees
• Minimum degree conditions for containing an \(r\)-regular \(r\)-connected spanning subgraph
• The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph

This page was built for publication: Good acyclic orientations of 4‐regular 4‐connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081883)