Associated bipartite graph

In graph theory , a branch of mathematics , each graph can be assigned to its associated bipartite graph .

construction

Let it be a finite graph with nodes and edges . The graph is assigned its associated bipartite graph as follows ${\displaystyle G}$ ${\displaystyle V(G)=\left\{v_{1},\ldots ,v_{n}\right\}}$ ${\displaystyle E(G)}$ ${\displaystyle G}$ ${\displaystyle B(G)}$

• the vertex set of is a disjoint union with , i. H. and each have the same cardinality as ${\displaystyle B(G)}$ ${\displaystyle X\cup Y}$ ${\displaystyle X=\left\{x_{1},\ldots ,x_{n}\right\},Y=\left\{y_{1},\ldots ,y_{n}\right\}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle V(G)}$
• for all is adjacent to ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$
• for is adjacent to if and only if . ${\displaystyle i\not =j}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle (v_{i}v_{j})\in E(G)}$

This graph is by construction a bipartite graph .

Applications

• Chordal bipartite graph

literature

• Peter Jan Pahl, Rudolf Damrath: Mathematical foundations of engineering informatics . Springer Verlag, Heidelberg 2000, ISBN 3-642-57013-5 , p. 558 ( limited preview in Google Book search).

Individual evidence

1. ^ R. Balakrishnan, K. Ranganathan: A textbook of graph theory. 2nd Edition. University text. Springer, New York 2012, ISBN 978-1-4614-4528-9 , chapter 9.5