Convex bipartite graph: Difference between revisions

Revision as of 04:38, 21 February 2016

Revision as of 19:38, 15 July 2016

Line 5:

==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'').

Line 18:

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

{{combin-stub}}

[[Category:Graph families]]

{{combin-stub}}