Full orientability of the square of a cycle.

zbMATH Open1363.05102arXiv1202.5721MaRDI QIDQ2823213FDOQ2823213

Authors: Fengwei Xu, Ko-Wei Lih, Weifan Wang 

Publication date: 6 October 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

Abstract: Let D be an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define m and M to be the minimum and the maximum number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying m <= k <= M. In this paper, we prove that the square of a cycle C_n of length n is fully orientable except n=6.

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

Recommendations

• Full orientability of graphs
• Full orientability of graphs with at most one dependent arc
• On preserving full orientability of graphs
• Chordal graphs are fully orientable.
• On fully orientability of 2-degenerate graphs

zbMATH Keywords

cycledigraphsquareacyclic orientationfull orientability

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Cited In (3)

• The minimum number of dependent arcs in \({C^3_{3k}}\)
• Full orientability of graphs with at most one dependent arc
• A note on full orientability of a graph

This page was built for publication: Full orientability of the square of a cycle.

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