3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路，如果G能够分解成若干个Pl，则称G存在{Pl}——分解，关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）；（ii）连通图G存在{P3，P4}-分解当且仅当G不是C3和奇树，这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况，并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.     

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.     

Complete subgraphs are elusive

We would like to decide whether a graph with a given vertex set has a certain property. We do this by probing the pairs of vertices one by one, i.e., asking whether a given pair of vertices is an edge or not. At each stage we make full use of the information we have up to that point. If there is an algorithm (a sequence of probes depending on the previous information) that allows us to come to a decision before checking every pair, the property is said to be incomplete, otherwise it is called complete or elusive. We show that the property of containing a complete subgraph with a given number of vertices is elusive. The proof also implies that the property of being r-chromatic (r fixed) is elusive.     

布尔函数的判定树复杂性及问题

设f（x₁,x₂,…,x_n）是一个布尔函数。如果计算f（x₁,x₂,…,x_n）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x₁,x₂,…,x_n）在循环群C_m×C_n的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

图的{P_4}—分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

Rainb ow Vertex-connection Numb er of Ladder and M¨obius Ladder

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder Ln, we determine the exact value of srvc(Ln) for n even. For n odd, upper and lower bounds of srvc(Ln) are obtained. We also give upper and lower bounds of the (strong) rainbow vertex-connection number of M¨obius Ladder.     

带弦的圈是协调图

称具有ｅ条边的简单图Ｇ为协调图，若存在由Ｇ的顶点集到模ｅ的整数群Ｚｅ的一个单射ｈ，使得导出映射ｈ＾＊：ｈ＾＊（ｕｖ）≡ｈ（ｕ）＋ｈ（ｖ）（ｍｏｄ ｅ）是一个由Ｇ的边集到Ｚｅ的双射，带弦的圈Ｃ′ｎ是由含ｎ个顶点的圈Ｃｎ上添一条连结两个不相邻顶点的边而得到的图。本文中证明了，除了ｎ＝６且弦端点在Ｃｎ上的距离为２的情况外，所有带弦的圈都是协调图。     

临界h-边-连通图的临界度

图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,I≤k.若G是k-临界h-边-连通但不(k 1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h 1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk 1.     

On hamiltonicity of 2-connected claw-free graphs

A graph G has the hourglass property if every induced hourglass S (a tree with a degree sequence 22224) contains two non-adjacent vertices which have a common neighbor in G - V(S).For an integer k ≥ 4,...     

Heptavalent Symmetric Graphs with Certain Conditions

A graph Γ is said to be symmetric if its automorphism group Aut(Γ)acts transitively on the arc set of Γ.We show that if Γ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group G of automorphisms,then either G is normal in Aut(Γ),or Aut(Γ)contains a non-abelian simple normal subgroup T such that G≤T and(G,T)is explicitly given as one of 11 possible exceptional pairs of non-abelian simple groups.If G is arc-transitive,then G is always normal in Aut(r),and if G is regular on the vertices of Γ,then the number of possible exceptional pairs(G,T)is reduced to 5.     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

On claws belonging to every tournament

A directed graph is said to ben-unavoidable if it is contained as a subgraph by every tournament onn vertices. A number of theorems have been proven showing that certain graphs aren-unavoidable, the first being Rédei's results that every tournament has a Hamiltonian path. M. Saks and V. Sós gave more examples in [6] and also a conjecture that states: Every directed claw onn vertices such that the outdegree of the root is at most [n/2] isn-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result:any claw of rootdegreen/4 is n-unavoidable.     

平面图的k-重(2k+2)-染色

G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,则称φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G...     

Path-pairability of infinite planar grids

Periodica Mathematica Hungarica - For a given integer $$k\ge 1$$ , a graph G with at least 2k vertices is called k-path-pairable, if for any set of k disjoint pairs of vertices, $$s_i,t_i$$ ,...     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

6p阶可解对称图的分类

设ｘ是简单无向图，Ｇ是Ａｕｔ（Ｘ）的一个于群，Ｘ称为Ｇ－对称的，如果Ｇ在ｘ的１－孤（即两相邻顶点构成的有序偶）集合上的作用是传递的；ｘ称为对称图，如果Ｘ是Ａｕｔ（ｘ）－对称的；ｘ称为可解对称的，如果Ａｕｔ（Ｘ）包含可解子群Ｇ，使Ｘ是Ｇ－对称的．本文给出了具有６Ｐ个顶点的可解对称图的一个分类，这里ｐ≥５是素数．     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.