The minimum number of dependent arcs and a related parameter of generalized Mycielski graphs
Abstract
Let D be an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let dmin(G) denote the minimum number of dependent arcs over fill acyclic orientations of G. Let G(Vo, Eo) be a graph with vertex set (Equation). and edge set E0. The generalized Mycielski graph Mm(G) of G, m > 0, has vertex set (Equation)., where (Equation)., and edge set (Equation)., where (Equation). We generalize results concerning dmin(M 1(G)) in K. L. Collins, K. Tysdal, J. Graph Theory 46(2004), 285-296, to dmin(Mm(G)). The underlying graph of a Hasse diagram is called a cover graph. Let c[G) denote the the minimum number of edges to be deleted from a graph G to get a cover graph. Analogue results about c{G) are also obtained.
