A study of 3-arc graphs

作者：Knor Martin^*; Xu Guangjun; Zhou Sanming

来源：Discrete Applied Mathematics, 2011, 159(5): 344-353.

DOI：10.1016/j.dam.2010.12.007

• 3-arc graph
• Domination number
• Independence number
• Chromatic number
• Arc-coloring

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have the arcs of G as vertices such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.

• 出版日期2011-3-6