Convex bipartite graph: Difference between revisions

Revision as of 19:38, 15 July 2016

Latest revision as of 10:47, 26 June 2025

(15 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Two-sided graph with consecutive neighbors}}

{{Use list-defined references|date=January 2025}}

{{CS1 config|mode=cs1}}

[[File:Convex bipartite graphs.svg|thumb|400px|Both graphs are convex bipartite graphs, because at least one side has edges with consecutive vertices on the other side (when properly ordered). The first is also '''biconvex''', because ''both'' sides have this property with the same vertex ordering, while the second is only convex for one side but cannot be made convex for both sides simultaneously (with any vertex ordering), making it '''singly convex'''.]]

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 14 ⟶ 10:

==References==

{{reflist|refs=

*{{cite journal|author=W. Lipski Jr.|author2=[[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|url=http://www.springerlink.com/content/u18656lrg6424n3u/|accessdate=2009-07-20}}

*{{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}}

*<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|urlhdl=http://www.springerlink.com/content/u18656lrg6424n3u2142/74215|accessdates2cid=200939361123|hdl-07-20access=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=http://books.google.com/?id=RrtXSKMAmWgC&pg=PA128&lpg=PA128&dq=%22a+bipartite+graph+is+a+convex+graph%22|accessdate=2009-07-20}}

*{{cite book|title=Graph classes: a survey|author=[[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=94|url=http://books.google.com/?id=es9ZbB6qHRYC&pg=PA94&lpg=PA94&dq=%22convex+if+there+is+an+ordering%22|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=httphttps://books.google.com/books?id=RrtXSKMAmWgC&pg=PA128&lpg=PA128&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=httphttps://booksarchive.google.comorg/?iddetails/graphclassessurv0000bran|url-access=es9ZbB6qHRYC&pg=PA94&lpgregistration|quote=PA94&dq=%22convex+convex if+ there+ is+ an+ ordering%22.|accessdate=2009-07-20}}</ref>

}}

[[Category:Graph families]]

[[Category:Bipartite graphs]]

{{combingraph-stub}}