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


Upper Bound on the Diameter of a Domination Dot-Critical Graph
Authors:Michitaka Furuya  Masanori Takatou
Affiliation:1. Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo, 162-8601, Japan
Abstract:A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k??? 3 and diameter d and if G has no critical vertices, then d??? 2k?3.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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