共查询到19条相似文献,搜索用时 774 毫秒
1.
本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数. 相似文献
2.
3.
图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了:(1)一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;(2)确定了圈、轮图、完全图、完全二部图的强符号全控制数的值. 相似文献
4.
5.
6.
特殊图类的符号控制数 总被引:2,自引:1,他引:1
王军秀 《纯粹数学与应用数学》2005,21(1):59-61
图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值. 相似文献
7.
对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图. 相似文献
8.
我们分别用γ(G),β(G)和α(G)表示图G的控制数、匹配数和覆盖数,对任意连通图,有γ(G)≤β(G)≤α(G)成立,1998年,Randerath和Volkmann给出了控制数等于覆盖数的图的特征,本文首先证明了匹配数与控制数相等的图其最小度不超过2,而后给出了最小度为2的图的结构性质。 相似文献
9.
令G为简单图.sα(G)等于图G的无符号拉普拉斯特征值α次幂的总和,其中α为实数且α≠0,1.本文我们得到一些连通图的sα(G)的新的界,并给出了正则图的Mycielskian图、正则图及半正则二部图的Double图这些特殊图类的sα(G)的新的界.由这些结论的特殊情况可得到相应图的关联能量的界. 相似文献
10.
11.
We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n2 log5 n) time and O(n2) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs. 相似文献
12.
In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices. 相似文献
13.
Jiuqiang Liu 《Journal of Graph Theory》1993,17(4):495-507
A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. © 1993 John Wiley & Sons, Inc. 相似文献
14.
In this paper, we determine the unique graph with minimum distance spectral radius among all connected bipartite graphs of order with a given matching number. Moreover, we characterize the graphs with minimal distance spectral radius in the class of all connected bipartite graphs with a given vertex connectivity. 相似文献
15.
In this paper we extend the notion of weak degree domination in graphs to hypergraphs and find relationships among the domination
number, the weak edge-degree domination number, the independent domination number and the independence number of a given hypergraph. 相似文献
16.
17.
On the 2-rainbow domination in graphs 总被引:2,自引:0,他引:2
The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K2. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp. 相似文献
18.
19.
In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition G[H] of two non-complete connected graphs G and H is equal to the clique domination number of G. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the graphs involved. 相似文献