| 词条 | Chordal bipartite graph |
| 释义 |
In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. [1]A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows. CharacterizationsChordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices. They are closely related to strongly chordal graphs. By definition, chordal bipartite graphs have a forbidden subgraph characterization as the graphs that do not contain any induced cycle of length 3 or of length at least 5 (so-called holes) as an induced subgraph. Thus, a graph G is chordal bipartite if and only if G is triangle-free and hole-free. In {{harvtxt|Golumbic|1980}}, two other characterizations are mentioned: B is chordal bipartite if and only if every minimal edge separator induces a complete bipartite subgraph in B if and only if every induced subgraph is perfect elimination bipartite. Martin Farber has shown: A graph is strongly chordal if and only if the bipartite incidence graph of its clique hypergraph is chordal bipartite. [2]A similar characterization holds for the closed neighborhood hypergraph: A graph is strongly chordal if and only if the bipartite incidence graph of its closed neighborhood hypergraph is chordal bipartite.[3] Another result found by Elias Dahlhaus is: A bipartite graph B = (X,Y,E) is chordal bipartite if and only if the split graph resulting from making X a clique is strongly chordal.[4] A bipartite graph B = (X,Y,E) is chordal bipartite if and only if every induced subgraph of B has a maximum X-neighborhood ordering and a maximum Y-neighborhood ordering.[5] Various results describe the relationship between chordal bipartite graphs and totally balanced neighborhood hypergraphs of bipartite graphs. [6]A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in.[7] A bipartite graph is chordal bipartite if and only if its adjacency matrix is totally balanced if and only if the adjacency matrix is Gamma-free. [8]RecognitionChordal bipartite graphs can be recognized in time {{nowrap|O(min(n2, (n + m) log n))}} for a graph with n vertices and m edges.[9]Complexity of problemsVarious problems such as Hamiltonian cycle,[10] Steiner tree [11] and Efficient Domination [12] remain NP-complete on chordal bipartite graphs. Various other problems which can be solved efficiently for bipartite graphs can be solved more efficiently for chordal bipartite graphs as discussed in [13]Related graph classesEvery chordal bipartite graph is a modular graph. The chordal bipartite graphs include the complete bipartite graphs and the bipartite distance-hereditary graphs.[14] Notes1. ^{{harvtxt|Golumbic|1980}}, p. 261, {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Definition 3.4.1, p. 43. 2. ^{{harvtxt|Farber|1983}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 3.4.1, p. 43. 3. ^{{harvtxt|Brandstädt|1991}} 4. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Corollary 8.3.2, p. 129. 5. ^{{harvtxt|Dragan|Voloshin|1996}} 6. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorems 8.2.5, 8.2.6, pp. 126–127. 7. ^{{harvtxt|Huang|2006}} 8. ^{{harvtxt|Farber|1983}} 9. ^{{harvtxt|Lubiw|1987}}; {{harvtxt|Paige|Tarjan|1987}}; {{harvtxt|Spinrad|1993}}; {{harvtxt|Spinrad|2003}}. 10. ^{{harvtxt|Müller|1996}} 11. ^{{harvtxt|Müller|Brandstädt|1987}} 12. ^{{harvtxt|Lu|Tang|2002}} 13. ^{{harvtxt|Spinrad|2003}}. 14. ^Chordal bipartite graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30. References{{refbegin|30em}}
| last = Brandstädt | first = Andreas | authorlink = Andreas Brandstädt | title = Classes of bipartite graphs related to chordal graphs | journal = Discrete Applied Mathematics | volume = 32 | pages = 51–60 | year = 1991 | doi=10.1016/0166-218x(91)90023-p}}.
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Dragan | first2 = Feodor | last3 = Chepoi | first3 = Victor | last4 = Voloshin | first4 = Vitaly | title = Dually Chordal Graphs | journal = SIAM Journal on Discrete Mathematics | volume = 11 | pages = 437–455 | year = 1998 | doi=10.1137/s0895480193253415}}.
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Le | first2 = Van Bang | last3 = Spinrad | first3 = Jeremy | title = Graph Classes: A Survey | publisher = SIAM Monographs on Discrete Mathematics and Applications | year = 1999 | isbn = 0-89871-432-X}}.
| last1 = Dragan | first1 = Feodor | last2 = Voloshin | first2 = Vitaly | title = Incidence graphs of biacyclic hypergraphs | journal = Discrete Applied Mathematics | volume = 68 | pages = 259–266 | year = 1996 | doi=10.1016/0166-218x(95)00070-8}}.
| last = Farber | first = M. | doi = 10.1016/0012-365X(83)90154-1 | issue = 2–3 | journal = Discrete Mathematics | pages = 173–189 | title = Characterizations of strongly chordal graphs | volume = 43 | year = 1983}}.
| last = Golumbic | first = Martin Charles | title = Algorithmic Graph Theory and Perfect Graphs | publisher = Academic Press | year = 1980 | isbn = 0-12-289260-7}}.
| last = Huang | first = Jing | doi = 10.1016/j.jctb.2006.01.001 | journal = Journal of Combinatorial Theory, Series B | pages = 673–683 | title = Representation characterizations of chordal bipartite graphs | volume = 96 | issue = 5 | year = 2006}}.
| last1 = Lu | first1 = Chin Lung | last2 = Tang | first2 = Chuan Yi | title = Weighted efficient domination on some perfect graphs | journal = Discrete Applied Mathematics | volume = 117 | pages = 163–182 | year = 2002 | doi=10.1016/s0166-218x(01)00184-6}}.
| last = Lubiw | first = A. | authorlink = Anna Lubiw | doi = 10.1137/0216057 | issue = 5 | journal = SIAM Journal on Computing | pages = 854–879 | title = Doubly lexical orderings of matrices | volume = 16 | year = 1987}}.
| last = Müller | first = Haiko | title = Hamilton circuits in chordal bipartite graphs | journal = Discrete Mathematics | volume = 156 | pages = 291–298 | year = 1996 | doi=10.1016/0012-365x(95)00057-4}}.
| last1 = Müller | first1 = Haiko | last2 = Brandstädt | first2 = Andreas | author2-link = Andreas Brandstädt | title = The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs | journal = Theoretical Computer Science | volume = 53 | pages = 257–265 | year = 1987 | doi=10.1016/0304-3975(87)90067-3}}.
| last1 = Paige | first1 = R. | last2 = Tarjan | first2 = R. E. | author2-link = Robert Tarjan | doi = 10.1137/0216062 | issue = 6 | journal = SIAM Journal on Computing | pages = 973–989 | title = Three partition refinement algorithms | volume = 16| year = 1987
| last = Spinrad | first = Jeremy | doi = 10.1016/0020-0190(93)90209-R | issue = 2 | journal = Information Processing Letters | pages = 229–235 | title = Doubly lexical ordering of dense 0–1 matrices | volume = 45 | year = 1993}}.
| last = Spinrad | first = Jeremy | title = Efficient Graph Representations | publisher = Fields Institute Monographs, American Mathematical Society | year = 2003 | isbn = 0-8218-2815-0}}.{{refend}} 2 : Graph families|Bipartite graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。