直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.     

连通的欧拉生成子图

本文证明了:若 G 是一个 p 个顶点的、2-边-连通简单图,其边数,q≥((p-4)/2)+7.则除 K_(2,5)外,G 有连通的欧拉生成子图.当 q=((p-4)/4)+6和 k(G)=2时,本文给出了全部6个极图.     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

无爪图中不相邻子图P_4和K_1度和条件下的哈密尔顿连通性

研究子图的度和图的哈密尔顿性的关系,证明图G是一个n阶3-连通无爪图且最小度δ(G)≥4,如果图G中任意两个分别同构于P_4,K_1的不相邻子图H_1,H_2满足d(H_1)+d(H_2)≥n,则图G是哈密尔顿连通.     

超欧拉图、可折叠图及匹配

如果图G有一个生成的欧拉子图,则称G是超欧拉图.用α′(G)表示G中最大独立的边的数目.本文证明了:若G是一个2-边连通简单图且α′(G)≤2,则G要么是可折叠图,要么存在G的某个连通子图H,使得对某个正整数t≥2,约化图G/H是K_(2.t.)推广了[Lai H J,Yan H.Supereulerian graphs and matchings.Appl.Math.Lett.,2011,24:1867-1869]中的一个主要结果.并且证明了上述文献中提出的一个猜想:3一边连通且α′(G)≤5的简单图是超欧拉图当且仅当它不可收缩成Petersen图.     

无爪图中点不相交的特殊四阶子图

如果图中不存在同构于K_(1.3)的诱导子图,则称这样的图为无爪图.令K_4~-表示从K_4中去掉一条边后得到的图.Faudree等人研究了无爪图中点不交三角形的个数与其最小度之间的关系,受此启发,我们研究了无爪图中点不交的K_4~-个数与其最小度以及阶数之间的关系.设G是阶数为n且最小度为δ≥5的无爪图,我们证明了G中包含至少((δ-4)/(7δ-8))n个点不交的K_4~-.作为推论,每—个阶数n≥28且δ(n/7)等的无爪图至少包含(n-7)-2个点不交的K_4~-.     

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

“关于Γ-图的判定”中的猜测问题

本刊1988年第4期的“关于Г-图的判定”一文中有一个猜测: 猜测 G是Г-图当且仅当G中不含如下的子图为导出子图: (1) C_(2n 1),n≥2;(2)K_3·3K_2(i),0≤i≤3;(3)5K_3. 这个猜测的结论是不成立的.举例说明如下: 设G为图1或图2所示的图.它的所有导出子图中,没有C_(2n 1)(n≥2)或K_3·3K_2(i)和     

两类完全三部图的图因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为S_λ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LS_λ(F,G),是G中所有与F同构的子图的一个分拆{B_i},使得每个B_i均构成一个S_λ(F,G).当λ=1时,λ可省略不写.在[Ars Combin.,2010,96:321-329]中已经得到了LS_λ(K_(1,2),K_(v,v))的存在谱.本文证明了当v≡4(mod 12)时,存在LS(F,K_(v,v,v)),这里F∈{K_(1,3),K_(2,2)}.     

Completely connected clustered graphs

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

Decomposing planar cubic graphs

The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.     

On powers and centers of chordal graphs

A graph is chordal if every cycle of length strictly greater than three has a chord. A necessary and sufficient condition is given for all powers of a chordal graph to be chordal. In addition, it is shown that for connected chordal graphs the center (the set of all vertices with minimum eccentricity) always induces a connected subgraph. A relationship between the radius and diameter of chordal graphs is also established.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

Compact Compatible Topologies for Posets and Graphs

A topology on the vertex set of a comparability graph G is said to be compatible (respectively, weakly compatible) with G if each induced subgraph (respectively, each finite induced subgraph) is topologically connected if and only it it is graph-connected; a weakly compatible topology on the vertex set of a graph completely determines the graph structure. We consider here the problem of deciding whether or not a comparability graph has a compact compatible or weakly compatible topology and in the case of graphs with small cycles, hence in the case of trees, we give a characterization.     

蕴含K4＋P2-可图序列的刻划

对于给定的图H,若存在可图序列π的一个实现包含H作为子图,则称π为蕴含H-可图的．Gould等人考虑了下述极值问题的变形：确定最小的偶整数σ（H,n）,使得每个满足σ（π）≥σ（H,n）的n项可图序列π=（d1,d2,…,dn）是蕴含H-可图的,其中σ（π）=∑di．本文刻划了蕴含K4＋P2-可图序列,其中K4＋P2是向致的一个顶点添加两条悬挂边后构成的简单图．这一刻划导出σ（K4＋P2,n）的值．     

A characterization of radius-critical graphs

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

含偶圈图的Laplacian 谱刻画

设 H(K_{1,5},P_n,C_l)是由路 P_n的两个悬挂点分别粘上星图K_{1,5}的悬挂点和圈 C_l的点所得的单圈图. 若两个二部图是关于Laplacian 矩阵同谱的, 则它们的线图是邻接同谱的, 两个邻接同谱图含有相同数目的同长闭回路. 如果任何一个与图G关于Laplacian 同谱图都与图G 同构, 那么称图G可由其Laplacian 谱确定. 利用图与线图之间的关系证明了H(K_{1,5},P_n,C_4)、H(K_{1,5},P_n,C_6) 由它们的Laplacian谱确定.