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

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

2012-02-29

arxiv.org/abs/1202.6461v1

Mathematics

Combinatorics

13 pages, accepted by Utilitas Mathematica on January 14, 2010

Scientific paper

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_k(G) of G is defined. Note that M_1(G) is the usual Mycielskian of G. We generalize results concerning m(M_1(G)) in K. L. Collins, K. Tysdal, J. Graph Theory, 46 (2004), 285-296, to m(M_k(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.

Affiliated with

Also associated with

No associations

Rating

The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523588