首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Constructing connected bicritical graphs with edge-connectivity 2
Authors:Xue-gang Chen  Shinya Fujita  Michitaka Furuya  Moo Young Sohn
Institution:1. Department of Mathematics, North China Electric Power University, Beijing 102206, China;2. Department of Mathematics, Gunma National College of Technology, Maebashi 371-8530, Japan;3. Department of Mathematical Information Science, Tokyo University of Science 1-3 Kagurazaka, Sinjuku-ku, Tokyo 162-8601, Japan;4. Department of Mathematics, Changwon National University, Changwon, 641-773, Republic of Korea
Abstract:A graph G is said to be bicritical if the removal of any pair of vertices decreases the domination number of G. For a bicritical graph G with the domination number t, we say that G is t-bicritical. Let λ(G) denote the edge-connectivity of G. In 2], Brigham et al. (2005) posed the following question: If G is a connected bicritical graph, is it true that λ(G)3?In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected t-bicritical graphs with edge-connectivity 2 for every integer t5. Furthermore, we give some sufficient conditions for a connected 5-bicritical graph to have λ(G)3.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号