On the connectivity of diamond-free graphs
- 作者：Peter Dankelmann ; Angelika Hellwig ; Lutz Volkmann
- 关键词：Connectivity ; Minimum degree ; Diamond-free graph ; none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4NT9G6D-4&_mathId=mml13&_user=10&_cdi=5629&_rdoc=10&_acct=C000050221&_version=1&_user
- 刊名：Discrete Applied Mathematics
- 出版年：2007
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：1 October 2007
- 卷：155
- 期：16
- 页码：2111-2117
- 文件大小：147 K
摘要
Let 050221&_version=1&_userid=10&md5=dd315bce644bdf0598077b8ac8aba052" title="Click to view the MathML source">G be a graph of order 050221&_version=1&_userid=10&md5=1fafdbcd23913e992be6314bc8e7cfc2" title="Click to view the MathML source">n(G), minimum degree 050221&_version=1&_userid=10&md5=2173f0959281cdadb54dee1992e97d13" title="Click to view the MathML source">δ(G) and connectivity 050221&_version=1&_userid=10&md5=d472613248f3a251e68315e41c7311d0" title="Click to view the MathML source">κ(G). Chartrand and Harary [Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61–63] gave the following lower bound on the connectivity
050221&_version=1&_userid=10&md5=ac7fa15ea7881d2765f32bbc4462b216" title="Click to view the MathML source">κ(G) 2δ(G)+2-n(G). |
Topp and Volkmann [Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695–700] improved this bound to 050221&_version=1&_userid=10&md5=0f6ab12c48474dedb08593ab3b2aae57" title="Click to view the MathML source">κ(G)4δ(G)-n(G), if 050221&_version=1&_userid=10&md5=d9a59e6497ceda166c4d6217206f2dad" title="Click to view the MathML source">G is bipartite and 050221&_version=1&_userid=10&md5=55905e803f50cecdde94856b78c792e6" title="Click to view the MathML source">κ(G)<δ(G). In this paper, we show that this result remains valid for diamond-free graphs with 050221&_version=1&_userid=10&md5=ae436c42990320a04567d4c068d7e730" title="Click to view the MathML source">δ(G)3. A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge.
4δ(G)-n(G), if 050221&_version=1&_userid=10&md5=d9a59e6497ceda166c4d6217206f2dad" title="Click to view the MathML source">G is bipartite and 050221&_version=1&_userid=10&md5=55905e803f50cecdde94856b78c792e6" title="Click to view the MathML source">κ(G)<δ(G). In this paper, we show that this result remains valid for diamond-free graphs with 050221&_version=1&_userid=10&md5=ae436c42990320a04567d4c068d7e730" title="Click to view the MathML source">δ(G)3. A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge.Furthermore, we show that the above bounds can be improved significantly for graphs with 050221&_version=1&_userid=10&md5=7799787165932b41b7c5faa710022931" title="Click to view the MathML source">δ(G)3 and no 4-cycle, namely, if 050221&_version=1&_userid=10&md5=0c50d851ce3d90f3bce68639bb76b350" title="Click to view the MathML source">κ(G)<δ(G), then
| 050221&_version=1&_userid=10&md5=594604e7d4797cc5df037efc679ba552" title="Click to view the MathML source">κ(G)2δ(G)2+2-2δ(G)-n(G). |
For graphs that, in addition, contain no 3-cycle, we improve this bound even further.