Abstract | ||
---|---|---|
Recently, some sufficient conditions for a digraph to have maximum connectivity or high superconnectivity have been given in terms of a new parameter which can be thought of as a generalization of the girth of a graph. In this paper similar results are derived for bipartite digraphs and graphs showing that, in this case, all the known conditions can be improved. As a corollary, it is shown that any bipartite graph of girth g and diameter D ⩽ g − 2 (respectively D ⩽ g − 1) has maximum vertex-connectivity (respectively maximum edge-connectivity). This implies a result of Plesnik and Znám stating that any bipartite graph with diameter three is maximally edge-connected. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1016/0166-218X(95)00097-B | Discrete Applied Mathematics |
Keywords | Field | DocType |
bipartite graph,maximum connectivity | Odd graph,Discrete mathematics,Complete bipartite graph,Combinatorics,Edge-transitive graph,Graph power,Bipartite graph,Foster graph,Pancyclic graph,Triangle-free graph,Mathematics | Journal |
Volume | Issue | ISSN |
69 | 3 | Discrete Applied Mathematics |
Citations | PageRank | References |
21 | 1.15 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
J. Fàbrega | 1 | 305 | 22.43 |
M. A. Fiol | 2 | 816 | 87.28 |