Independent edges in bipartite graphs obtained from orientations of graphs

✍ Scribed by J. G. Gimbel; K. B. Reid

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 800 KB
• Volume: 18
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190180509

✦ Synopsis

Abstract

Given a digraph D on vertices v~1~, v~2~, ⃛, v~n~, we can associate a bipartite graph B(D) on vertices s~1~, s~2~, ⃛, s~n~, t~1~, t~2~, ⃛, t~n~, where s~i~t~j~ is an edge of B(D) if (v~i~, v~j~) is an arc in D. Let O~G~ denote the set of all orientations on the (undirected) graph G. In this paper we will discuss properties of the set S(G) := {β~1~ (B(D))) | D ≅ O~G~}, where β~1~ is the edge independence number.

In the first section we present some background and related concepts. We show that sets of the form S(G) are convex and that max S(G) ≦ 2 min S(G). Furthermore, this completely characterizes such sets.

In the second section we discuss some bounds on elements of S(G) in terms of more familiar graphical parameters.

The third section deals with extremal problems. We discuss bounds on elements of S(G) if the order and size of G are known, particularly when G is bipartite. In this section we exhibit a relation between max S(G) and the concept of graphical closure.

In the fourth and final section we discuss the computational complexity of computing min S(G) and max S(G). We show that the first problem is NP‐complete and that the latter is polynomial.