TY - JOUR
AU - A.Sudhakar Reddy, Dr.V. Ramalatha,
PY - 2024/08/17
Y2 - 2024/10/13
TI - GENERALIZED ON COMPLEXITY OF SET OF BIPARTITE GRAPHS AND APPLICATIONS
JF - Utilitas Mathematica
JA - A Canadian journal of applied mathematics, computer science and statistics
VL - 121
IS -
SE - Articles
DO -
UR - https://utilitasmathematica.com/index.php/Index/article/view/2023
SP - 163-173
AB - <p>In this present paper The complexity x<sub>c</sub>(P) of a P is the minimum number of facets of a that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let G be the convex hull of the sets of G. Since G is perfect, it is easy to see that nxc(G) n + m. We improve both of these bounds. For the upper bound, we show that xc(G) is O(), which is an improvement when G has quadratically many edges. For the lower bound, we prove that xc(G) is Ω(log n) when G is the incidence graph of a finite projective plane. We also provide the obvious upper and lower bounds are both essentially fixed.</p>
ER -