Convex bipartite graph: Difference between revisions

Revision as of 07:34, 18 November 2024

Revision as of 06:00, 7 February 2025

Line 1:

{{NoUse footnoteslist-defined references|date=NovemberJanuary 20242025}}

{{CS1 config|mode=cs1}}

In the [[mathematical]] field of [[graph theory]], a '''convex bipartite graph''' is a [[bipartite graph]] with specific properties.

A bipartite graph, (''U'' ∪ ''V'', ''E''), is said to be convex over the vertex set ''U'' if ''U'' can be [[enumeration|enumerated]] such that for all ''v'' ∈ ''V'' the vertices adjacent to ''v'' are consecutive. Convexity over ''V'' is defined analogously. A bipartite graph (''U'' ∪ ''V'', ''E'') that is convex over both ''U'' and ''V'' is said to be '''biconvex''' or '''doubly convex'''.{{r|lp81|lw97|s03|bls99}}

Convexity over ''V'' is defined analogously. A bipartite graph (''U'' ∪ ''V'', ''E'') that is convex over both ''U'' and ''V'' is said to be '''biconvex''' or '''doubly convex'''.

==Formal definition==

Let ''G'' = (''U'' ∪ ''V'', ''E'') be a bipartite graph, i.e., the vertex set is ''U'' ∪ ''V'' where ''U'' ∩ ''V'' = ∅.

Let ''N''_''G''(''v'') denote the neighborhood of a vertex ''v'' ∈ ''V''.

The graph ''G'' is '''convex''' over ''U'' if and only if there exists a [[bijective]] mapping, ''f'': ''U'' → {1, …, |''U''|}, such that for all ''v'' ∈ ''V'',

for any two vertices ''x'',''y''&nbsp;∈&nbsp;''N''_''G''(''v'')&nbsp;⊆&nbsp;''U'' there does not exist a ''z''&nbsp;∉&nbsp;''N''_''G''(''v'') such that ''f''(''x'')&nbsp;<&nbsp;''f''(''z'')&nbsp;<&nbsp;''f''(''y'').

==See also==

Line 15 ⟶ 8:

==References==

{{reflist|refs=

*{{cite journal|author=W. Lipski Jr.|author2=Franco P. Preparata|author2-link=Franco P. Preparata|date=August 1981|title=Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems|journal=Acta Informatica|volume=15|issue=4|pages=329–346|doi=10.1007/BF00264533|hdl=2142/74215|s2cid=39361123|hdl-access=free}}

*{{cite journal|author=Ten-hwang Lai|author2=Shu-shang Wei|date=April 1997|title=Bipartite permutation graphs with application to the minimum buffer size problem|journal=Discrete Applied Mathematics|volume=74|issue=1|pages=33–55|doi=10.1016/S0166-218X(96)00014-5|url=http://citeseer.ist.psu.edu/old/lai94bipartite.html|accessdate=2009-07-20|doi-access=free}}

*<ref name=lp81>{{cite journal|author=W. Lipski Jr.|author2=Franco P. Preparata|author2-link=Franco P. Preparata|date=August 1981|title=Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems|journal=Acta Informatica|volume=15|issue=4|pages=329–346|doi=10.1007/BF00264533|hdl=2142/74215|s2cid=39361123|hdl-access=free}}</ref>

*{{cite book|title=Efficient graph representations|author=Jeremy P. Spinrad|year=2003|publisher=[[American Mathematical Society|AMS]] Bookstore|isbn= 978-0-8218-2815-1 |page=128|url=https://books.google.com/books?id=RrtXSKMAmWgC&dq=%22a+bipartite+graph+is+a+convex+graph%22&pg=PA128|accessdate=2009-07-20}}

*{{cite book|title=Graph classes: a survey|author=Andreas Brandstädt|author-link=Andreas Brandstädt|author2=Van Bang Le |author3=Jeremy P. Spinrad |year=1999|publisher=[[Society for Industrial and Applied Mathematics|SIAM]]|isbn=978-0-89871-432-6 |page=[https://archive.org/details/graphclassessurv0000bran/page/94 94]|url=https://archive.org/details/graphclassessurv0000bran|url-access=registration|quote=convex if there is an ordering.|accessdate=2009-07-20}}

*<ref name=lw97>{{cite journal|author=Ten-hwang Lai|author2=Shu-shang Wei|date=April 1997|title=Bipartite permutation graphs with application to the minimum buffer size problem|journal=Discrete Applied Mathematics|volume=74|issue=1|pages=33–55|doi=10.1016/S0166-218X(96)00014-5|url=http://citeseer.ist.psu.edu/old/lai94bipartite.html|accessdate=2009-07-20|doi-access=free}}</ref>

*<ref name=s03>{{cite book|title=Efficient graph representations|author=Jeremy P. Spinrad|year=2003|publisher=[[American Mathematical Society|AMS]] Bookstore|isbn= 978-0-8218-2815-1 |page=128|url=https://books.google.com/books?id=RrtXSKMAmWgC&dq=%22a+bipartite+graph+is+a+convex+graph%22&pg=PA128|accessdate=2009-07-20}}</ref>

*<ref name=bls99>{{cite book|title=Graph classes: a survey|author=Andreas Brandstädt|author-link=Andreas Brandstädt|author2=Van Bang Le |author3=Jeremy P. Spinrad |year=1999|publisher=[[Society for Industrial and Applied Mathematics|SIAM]]|isbn=978-0-89871-432-6 |page=[https://archive.org/details/graphclassessurv0000bran/page/94 94]|url=https://archive.org/details/graphclassessurv0000bran|url-access=registration|quote=convex if there is an ordering.|accessdate=2009-07-20}}</ref>

}}

[[Category:Graph families]]