泛连通图的Faudree-Schelp定理和哈密尔顿连通图的Ore定理的注记

In this note more short proofs are given for Faudree-Schelp theorem and Ore theorem.     

极小拟(k+1)连通图的最小度

给出了极小拟5连通图有围长大于或等于4的极小拟（k）＋1连通图的最小度。     

Hamiltonian Connected Claw-Free Graphs

A well-known result by O. Ore is that every graph of order n with d(u)+d(v)n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected (i.e., for every pair of vertices, there is a hamiltonian path joining them). In this paper, we show that every 3-connected claw-free graph G on at most 5–8 vertices is hamiltonian connected, where denotes the minimum degree in G. This result generalizes several previous results.Acknowledgments. The author would like to thank the referee for his important suggestions and careful corrections.Final version received: March 12, 2003Supported by the project of Nature Science Funds of China     

图的连通因子

连通因子问题与Hamilton问题和信息网络有着密切的联系．1993年，首先由M.Kano就该问题在[6]中提出了许多问题和猜想，接下来他又在[16]中提出了一些猜想，本文就连通因子问题在过去十年的主要进展进行了回顾并提出了若干可进一步研究的问题和猜想．     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

The Average Degree of Minimally Contraction‐Critically 5‐Connected Graphs

An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than .     

Weakly Connected Domination in Graphs

In the last 50 years, Graph theory has seen an explosive growth due to interaction with areas like computer science, electrical and communication engineering, Operations Research etc. Perhaps the fastest growing area within graph theory is the study of domination, the reason being its many and varied applications in such fields as social sciences, communication networks, algorithm designs, computational complexity etc. Henda C. Swart has rightly commented that the theory of domination in graphs is like a ‘growth industry’. There are several types of domination depending upon the nature of domination and the nature of the dominating set. In the following, we present weakly connected domination in connected graphs.     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

A Note on Almost Regular Graphs

It can easily be seen that a conjecture of Runge does not hold for a class of graphs whose members will be called “almost regular”. This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.     

A Note on Semi-coloring of Graphs

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least ${\lceil\frac{r}{2}\rceil}$ different {K ₂, C _i | i ≥ 3}-factors.     

图的k部划分的一个注记

设k≥2是一个整数。本文证明了任意有m条边的图都存在一个顶点的划分V_1,V_2…,V_k,使得e(V_1,V_2…,V_k)≥k-1/k m+k-1/2k((2m+1/4)~1/2-1/2)-(k-2)~2/8k,且max{e(V_i):1≤i≤k}≤m/k~2+(k-1)/2k~2((2m+1/4)~1/2-1/2+3/8-7k-4/8k~2.我们的结果改进了[Fan G.,Hou J.,Zeng Q.,A bound for judicious k-partitions of graphs,Discrete Appl.Math.,2014,179:86—99]的主要结论.     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

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.     

Ehrhart Series for Connected Simple Graphs

The Ehrhart ring of the edge polytope ${\mathcal{P}_G}$ for a connected simple graph G is known to coincide with the edge ring of the same graph if G satisfies the odd cycle condition. This paper gives for a graph which does not satisfy the condition, a generating set of the defining ideal of the Ehrhart ring of the edge polytope, described by combinatorial information of the graph. From this result, two factoring properties of the Ehrhart series are obtained; the first one factors out bipartite biconnected components, and the second one factors out a even cycle which shares only one edge with other part of the graph. As an application of the factoring properties, the root distribution of Ehrhart polynomials for bipartite polygon trees is determined.     

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.     

On Connected Resolving Decompositions in Graphs

For an ordered k-decomposition of a connected graph G and an edge e of G, the -code of e is the k-tuple where d(e, G _i) is the distance from e to G _i. A decomposition is resolving if every two distinct edges of G have distinct -codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim _d (G). A resolving decomposition of G is connected if each G _i is connected for 1 i k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 dim _d (G) cd(G) m for every connected graph G of size m 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m – 1 or m – 2. It is shown that each pair s, t of rational numbers with 0 < s t 1, there is a connected graph G of size m such that dim _d (G)/m = s and cd(G)/m = t.