首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 109 毫秒
1.
设λ是图G的一个特征值,如果存在属于λ的一个特征向量X=(x_1,x_2,…,x_n)~T,使得(?)x_i≠0,则λ称为图G的主特征值.将恰有两个主特征值的一个充要条件做了进一步推广,并在此基础上给出恰有两个主特征值的图的一些性质以及恰有两个主特征值的图的一些运算结果.  相似文献   

2.
图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.  相似文献   

3.
图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.  相似文献   

4.
图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.  相似文献   

5.
奇图的匹配可扩性   总被引:1,自引:0,他引:1       下载免费PDF全文
设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.  相似文献   

6.
设G=(X,Y;E)是一个偶图。如果|X|≥2|Y|-3且d(v)=3对任意v∈X,那么G含有K3.3的剖分。有例子表明|X|的下界在一定程度上是不可改进的。  相似文献   

7.
设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.若k=2,则称分数k-消去图为分数2-消去图.本文证明了当bind(G)≥2,并且δ(G)≥3时,G是分数2-消去图.  相似文献   

8.
单项式理想是多项式环中一类重要的理想,这类理想的生成元和超图的边之间可以一一对应.超图的边理想的很多代数性质和它的组合性质之间有密切的联系.根据线图、圈图和单项式理想的正则度的一些公式,通过构造合适的短正合列,给出了两类m-剖分图的边理想的正则度的精确公式,分别推广了m个顶点的线图和圈图的正则度公式.  相似文献   

9.
本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.  相似文献   

10.
一个近-三角剖分嵌入是指一个曲面上的嵌入图使得几乎所有的面都是三角形,至多只有一个可能的例外.文中作者证明了如下结论:如果一个图G 在球面S0(或环面S1)上有近-三角剖分嵌入,那么G在每一个可定向曲面Sk有近-三角剖分嵌入,其中k=h,h+1,\cdots ,\lfloor\frac{\beta(G)}{2}\rfloor$, 而h=0(或1)并且β(G)是图G的Betti数.特别地,G是上可嵌入的.  相似文献   

11.
An eigenvalue of a graph is main if it has an eigenvector, the sum of whose entries is not equal to zero. Extending previous results of Hagos and Hou et al. we obtain two conditions for graphs with given main eigenvalues. All trees and connected unicyclic graphs with exactly two main eigenvalues were characterized by Hou et al. Extending their results, we determine all bicyclic connected graphs with exactly two main eigenvalues.  相似文献   

12.
An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined.  相似文献   

13.
一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出一类正则二部图,它们是二面体群的凯莱图,这类图的单特征值中除了它的正、负度数之外还有0或者±1,而它们恰好是Petersdorf和Sachs所给出的单特征值范围内的中间取值.  相似文献   

14.
In this paper we determine all finite connected graphs whose spectrum contains exactly two negative eigenvalues. The main theorem says that a graph has exactly two negative eigenvalues if and only if its “canonical graph” (defined below) is one of nine particular graphs on 3, 4, 5 and 6 vertices.  相似文献   

15.
A graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. An eigenvalue of a graph is called main eigenvalue if it has an eigenvector such that the sum of whose entries is not equal to zero. In this paper, we show that there are exactly 25 connected integral graphs with exactly two main eigenvalues and index 3.  相似文献   

16.
对一个给定的简单图G,是否存在V(G)的一个2-划分(V1,V2)使得每个导出子图G[Vi]为森林?称该问题为导出森林2-划分问题.本文证明了对最大度为5的图该问题是NP-完全的,而对最大度≤4的图该问题多项式时间可解.  相似文献   

17.
The center of a graph is the set of vertices with minimum eccentricity. Graphs in which all vertices are central are called self-centered graphs. In this paper almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central vertices. The block structure of these graphs is described and constructions for generating such graphs are proposed. Embeddings of arbitrary graphs into ASC graphs are studied. In particular it is shown that any graph can be embedded into an ASC graph of prescribed radius. Embeddings into ASC graphs of radius two are studied in more detail. ASC index of a graph G is introduced as the smallest number of vertices needed to add to G such that G is an induced subgraph of an ASC graph.  相似文献   

18.
《Discrete Mathematics》2023,346(6):113373
The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

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