共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
3.
4.
(下整)和标号与排斥(下整)和标号是图的一种压缩表示.一个图G称为下整和图,若它同构于某个SQ+的下整和图.图Pn×K2称为梯子.本文给出了梯子细分图Ln*的定义,并确定了梯子细分图Ln*的排斥(下整)和数. 相似文献
5.
徐新萍 《数学的实践与认识》2009,39(10)
设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果. 相似文献
6.
7.
8.
9.
高度图的独立集复形 总被引:3,自引:0,他引:3
给定图G,称以G的所有独立集为单形的抽象复形I(G)为G的独立集复形.如果两个图G和H的独立集复形I(G)和I(H)的各阶同调群都是同构的,则称两个图是独立同调的.J(G)表示Gc的连通分支数,J3K2(G)表示Gc中同构于(3H2)c的连通分支数.本文研究了最小次δ(G)至少为其阶数|V(G)|减5的图G的独立集复形的结构,对满足δ(G)≥|V(C)|5,δ(H)≥|V(H)|-5的两个图G和H,(I)证明了,G和H独立同调的充要条件为J(G)=J(H),J3K2(G)=J3K2(H),且I(G)和I(H)的Euler示性数相同.(Ⅱ)给出了一个在图上计算I(G)的一维Betti数的方法,得到了一个I(G)是无圈复形的充要条件 相似文献
10.
主要讨论有限群G=N×MSL(3,C)的McKay箭图,及其对应的斜群代数∧V*G的截断箭图和截断代数的性质,证明了当3|(n+1),3|r时,其特殊截断代数的平凡扩张与斜群代数∧V*G同构. 相似文献
11.
12.
Louis Ibarra 《Discrete Applied Mathematics》2009,157(8):1737-1749
We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n3) time and of an interval graph in O(n2) time, where n is the number of vertices in the graph. 相似文献
13.
关于联图P_1VP_n的k-强优美性 总被引:1,自引:0,他引:1
本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果. 相似文献
14.
如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果. 相似文献
15.
The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs. 相似文献
16.
首先对开关图的自同构群进行了研究,随即讨论了它的点传递性,并得到Calyley图的开关图依然是Cayley图. 相似文献
17.
A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given. 相似文献
18.
图的spread定义为图的邻接矩阵的最大特征值与最小特征值的差.本文确定了n(n≥84)顶点四圈图中spread最大的唯一的图. 相似文献
19.
《Discrete Mathematics》2022,345(3):112734
In this paper, a complete classification of finite simple cubic vertex-transitive graphs of girth 6 is obtained. It is proved that every such graph, with the exception of the Desargues graph on 20 vertices, is either a skeleton of a hexagonal tiling of the torus, the skeleton of the truncation of an arc-transitive triangulation of a closed hyperbolic surface, or the truncation of a 6-regular graph with respect to an arc-transitive dihedral scheme. Cubic vertex-transitive graphs of girth larger than 6 are also discussed. 相似文献