On an interpolation property of outerplanar graphs

DOI10.1016/J.DAM.2005.07.004MaRDI QIDQ2581566zbMATH OpenOpenAlexFDO

Authors Ko-Wei Lih, Chen-Ying Lin, Li-Da Tong

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.07.004

zbMATH Keywords

acyclic orientationsdependent arcsdual of a graphoriented graph

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

Let \(D\) be an acyclic orientation of a graph \(G\). An arc of \(D\) is dependent if a directed cycle is created when it is reversed. Denote by \(d(D)\) the number of dependent arcs in \(D\). Let \(d_{\min}(G)\) be the minimum \(d(D)\), and \(d_{\max}(G)\) the maximum \(d(D)\), over all acyclic orientations \(D\) of \(G\). The authors measure \(d_{\min}(G)\) in terms of edge coverings of the weak dual of \(G\). They show \(G\) has an acyclic orientation with \(k\) dependent arcs if \(d_{\min}(G) \leq k \leq d_{\max}(G)\).

Recommendations

• Full orientability of graphs with at most one dependent arc
• The number of dependent arcs in an acyclic orientation
• Full orientability of graphs
• The minimum number of dependent arcs in \({C^3_{3k}}\)
• The minimum number of dependent arcs and a related parameter of generalized Mycielski graphs

Cites work

• Acyclic orientations of complete bipartite graphs
• Balanced graphs and noncovering graphs
• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Interpolation theorems for domination numbers of a graph
• The number of dependent arcs in an acyclic orientation
• TWO THEOREMS IN GRAPH THEORY

Cited in

(13)

• Independent arcs of acyclic orientations of complete \(r\)-partite graphs
• The number of dependent arcs in an acyclic orientation
• The connectivity of acyclic orientation graphs
• On fully orientability of 2-degenerate graphs
• Outerplanar graphs having the metric extension property. II
• Full orientability of graphs
• The minimum number of dependent arcs and a related parameter of generalized Mycielski graphs
• The minimum number of dependent arcs in \({C^3_{3k}}\)
• scientific article; zbMATH DE number 1439469 (Why is no real title available?)
• Graphs isomorphisms under edge-replacements and the family of amoebas
• A minimum degree condition for a 2-connected graph containing all possible orders of 2-connected subgraphs
• On preserving full orientability of graphs
• Full orientability of graphs with at most one dependent arc

This page was built for publication: On an interpolation property of outerplanar graphs

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