徐保根,周尚超.具有最大控制数的连通图的刻画(英文)[J].数学研究及应用,2000,20(4):523~528 |
具有最大控制数的连通图的刻画(英文) |
Characterization of Connected Graphs with Maximum Domination Number |
投稿时间:1997-11-02 修订日期:1999-07-01 |
DOI:10.3770/j.issn:1000-341X.2000.04.009 |
中文关键词: |
英文关键词:connected graph crown domination number domination critical graph |
基金项目: |
|
摘要点击次数: 1984 |
全文下载次数: 902 |
中文摘要: |
设G为一个P阶图,γ(G)表示G的控制数.显然γ(G)≤[p/2].本文的目的是刻画达到这个上界的连通图.主要结果:(1)当p为偶数时,γ(G)=p/2当且仅当G≈C4或者G为某连通图的冠;(2)当p为奇数时,γ(G)=(p-1)/2当且仅当G的每棵生成树为定理3.1中所示的两类树之一. |
英文摘要: |
Let G be a connected graph of order p, and let γ(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G≈C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1. |
查看全文 查看/发表评论 下载PDF阅读器 |