The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs

Original · EN

Let D be an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let m(G) denote the minimum number of dependent arcs over all acyclic orientations of G. For any k > 0, a generalized Mycielski graph Mₖ(G) of G is defined. Note that M₁(G) is the usual Mycielskian of G. We generalize results concerning m(M₁(G)) in K. L. Collins, K. Tysdal, J. Graph Theory, 46 (2004), 285-296, to m(Mₖ(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.