篇名 | Related the Connectivity of a Graph with its Complement |
---|---|
卷期 | 2 |
作者 | Chan, Hung-chang |
頁次 | 001-008 |
關鍵字 | Connectivity 、 Complement of graph 、 Join 、 Geodetic connectivity |
出刊日期 | 2010 |
There are a lot of papers discussing the connectivityof a graph and its complement graph. For example,it has been characterized that a graph G and its complement G are both have connectivity one or both are 2-connected. In this paper, we establish a simple formula to compute the connectivity of a graph that comes from the join of graphs. Based
on this formula, we derive an upper bound and a lower bound to the connectivity of the complement of a graph. We also show that if a k-connected graph G fulfills a certain condition related to its complement, then G is k-geodetically connected.