On the Spectral Radius of Trees with the Given Diameter d

Let T denote a tree with the diameter d(d≥2) and order n. Let P^*d,r,n-d-1denote the tree obtained by identifying the rth vertex of path Pd l and the center of starKl,K1,n-d-1, where r = r(d) is the integer part about d 2/2. Then p(T)≤ p(P^*d,r,n-d-1), andequality holds if and only if T≌P^*d,r,n-d-1     

Classification of Regular Planar Graphs with Diameter Two

In the present paper, the regular planar graphs with diameter two are classified.     

On the Maximum Spectral Radius of （m, n）-trees with Given Diameter

Let (V, U) be the vertex-partition of tree T as a bipartite graph. T is called an (m,n)-tree if |V|=m and |U| = n. For given positive integers m,n and d, the maximum spectral radius of all (m,n)-trees on diameter d are obtained, and all extreme graphs are determined.     

New Ore��s Type Results on Hamiltonicity and Existence of Paths of Given Length in Graphs

The well-known Ore??s theorem (see Ore in Am Math Mon 65:55, 1960), states that a graph G of order n such that d(x)?+?d(y)??? n for every pair {x, y} of non-adjacent vertices of G is Hamiltonian. In this paper, we considerably improve this theorem by proving that in a graph G of order n and of minimum degree ????? 2, if there exist at least n ? ?? vertices x of G so that the number of the vertices y of G non-adjacent to x and satisfying d(x)?+?d(y)??? n ? 1 is at most ?? ? 1, then G is Hamiltonian. We will see that there are graphs which violate the condition of the so called ??Extended Ore??s theorem?? (see Faudree et?al. in Discrete Math 307:873?C877, 2007) as well as the condition of Chvatál??s theorem (see Chvátal in J Combin Theory Ser B 12:163?C168, 1972) and the condition of the so called ??Extended Fan?? theorem?? (see Faudree et?al. in Discrete Math 307:873?C877, 2007), but satisfy the condition of our result, which then, only allows to conclude that such graphs are Hamiltonian. This will show the pertinence of our result. We give also a new result of the same type, ensuring the existence of a path of given length.     

The Strongly Simple Cycles with Given Rotation Pairs of an Interval Map

In this paper, we introduce the notion of the strongly simple cycles with some rotation pair for interval maps and prove that, if an interval map has a cycle with given rotation pair, then it, has a strongly simple cycle with the same rotation pair.     

Super-edge-graceful Labelings of Some Cubic Graphs

The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.     

Restricted Edge Connectivity of Binary Undirected Kautz Graphs

A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge connectivity, and is denoted by λ′(G). Let ξ(G) bethe minimum edge degree of graph G. It is known that λ′(G) ≤ξ(G) if G contains restrictededge cuts. Graph G is called maximal restricted edge connected if the equality holds in thethe preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to bemaximal restricted edge connected if n ≥ 2.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

On the Gracefulness of Two Family of the Hexagonal Graphs

Thegracefulgraphswaspresentedinl966.Sincethattime,manyresultshavebeenobtainedongacefulgraphsandit'smanyapplicationsappear(see[2j,L4j).Thegraceful-nessofP.XP.andC.XP,areprovedbythepaper[1],[3j,[5j,[6]-Followingthis,inthispaper,itisobtainedthatthegracefu1nessofthefamiliesofthehexagonalgraphsG,(n)andG2(n).Fornotationsandteminologiesonthegracelulgraphnotdefinedhere,wefollowthereference[3j-NowletG(V,E)beagraph,6bethelabelingoftheverticesofG,andforanyedgeuv,define6(uv)=lo(u)-o(v)Iitistheedge's…     

Non-bipartite Graphs with Third Largest Laplacian Eigenvalue Less Than Three

All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.     

图的树宽的分解定理

图的树宽问题是名的ＮＰ－困难问题。其分解原则在确定树宽的一般算法和特殊算法中有重要应用。本给出这方面的若干定理。     

Factor-Critical Graphs with Given Number of Maximum Matchings

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019) of China.     

几类可升分解的图

Ａｌａｖｉ等人在文献［１］中定义了图的一种新分解，即“升分解”，并且猜想：任意有正数条边的图都可升分解。本文证明了下面三类图可升分解，并得到了一些有意义的推论。１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ≥５）；２对称图可升分解；３对称图Ｇ的混合积（Ｇ；ｋ）可升分解。     

关于Abel群上Cayley图的Hamilton圈分解

设Ｇ（Ｆ，Ｔ∩Ｔ＾－１）是有限Ａｂｅｌ群Ｆ上的Ｃａｙｌｅｙ图，Ｔ∩Ｔ＾－１只含２阶元，此文证明了当Ｔ是Ｆ的极小生成元集时，若ｄ（Ｇ）＝２ｋ，则Ｇ是ｋ个边不相交的Ｈａｍｉｌｔｏｎ圈的并，若ｄ（Ｇ）＝２ｋ＋１，则Ｇ是ｋ个边不相交的Ｈａｍｉｌｔｏｎ圈与一个１－因子的并。     

图的最小填充的分解定理

在计算数学领域,稀疏矩阵的最小填充排序问题由于其重要的实际意义而受到重视。本文从图论的观点提出一种处理方法,即运用分解定理来处理一些特殊结构,从而导出一些特殊图的最小填充数。     

图的{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}-分解.     

图的{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}—分解.     

Almost Given Length Cycles in Digraphs

A digraph is called k-cyclic if it cannot be made acyclic by removing less than k arcs. It is proved that for every ε > 0 there are constants K and δ so that for every d ∈ (0, δn), every ε n²-cyclic digraph with n vertices contains a directed cycle whose length is between d and d + K. A more general result of the same form is obtained for blow-ups of directed cycles.     

On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.