Convex bipartite graph: Difference between revisions

Revision as of 18:50, 11 May 2010

Revision as of 03:41, 12 May 2010

Line 1:

In the [[mathematical]] field of [[graph theory]], a '''convex bipartite graph''' is a special kind of [[bipartite graph]] with specific properties.
A bipartite graph, <math>(''U,''&nbsp;∪&nbsp;''V'',&nbsp;''E'')</math>, is said to be convex over the vertex set <math>''U</math>'' if <math>''U</math>'' can be [[total order|ordered]] such that for all <math>''v\in ''&nbsp;∈&nbsp;''V</math>'' the vertices adjacent to <math>''v</math>'' are consecutive.

Convexity over <math>''V</math>'' is defined analogously. A bipartite graph <math>(''U,''&nbsp;∪&nbsp;''V'',&nbsp;''E'')</math> that is convex over both <math>''U</math>'' and <math>''V</math>'' is said to be '''biconvex''' or '''doubly convex'''.

==Formal definition==

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

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

The graph ''G'' is '''convex''' over ''U'' if and only if there exists a bijective mapping, ''f'':&nbsp;''U''&nbsp;→&nbsp;{&nbsp;1,&nbsp;2,&nbsp;...,&nbsp;|''U''|&nbsp;&minus;&nbsp;1,&nbsp;|''U|''}, such that for all ''v''&nbsp;∈&nbsp;''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==