围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

Covering Planar Graphs with a Fixed Number of Balls

In this note we prove that there exists a constant ρ such that any planar graph G of diameter ≤ 2R can be covered with at most ρ balls of radius R, a result conjectured by Gavoille, Peleg, Raspaud, and Sopena in 2001.     

一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n ₁, . . . , n _k ) of positive integers such that n ₁ + · · · + n _k = n there exists a partition (V ₁, . . . , V _k ) of the vertex set of G such that for each ${i \in \{1,\ldots,k\}}$ , V _i induces a connected subgraph of G on n _i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n ? 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.     

Paired Domination Vertex Critical Graphs

Let γ _pr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _pr (G – v) < γ _pr (G). We call these graphs γ _pr -critical. In this paper, we present a method of constructing γ _pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ _pr -critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191).     

点可迁图中的正则因子

设图G是一个K-正则连通点可迁图.如果G不是极大限制性边连通的,那么G含有一个(k-1)-因子,它的所有分支都同构于同一个阶价于k和2k-3之间的点可迁图.此结果在某种程度上加强了Watkins的相应命题:如果k正则点可迁图G不是k连通的,那么G有一个因子,它的每一个分支都同构于同一个点可迁图.     

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

On Planar Toeplitz Graphs

We describe several classes of finite, planar Toeplitz graphs and present results on their chromatic number. We then turn to counting maximal independent sets in these graphs and determine recurrence equations and generating functions for some special cases.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

极大全控点临界图

图G的点集S如果满足:VG-S(或VG)中每个点相邻于S中的某个点(或而不是它本身),则称点集S是一个控制集(或全控制集).图G的所有控制集(或全控制集)中最小基数的控制集(或全控制集)中的点数,称为控制数(或全控数),记为γ(G)(或γt(G)).在这篇文章中我们特征化γt-临界图且满足γt(G)=n-Δ(G)的图特征,这回答了Goddard等人提出的一个问题.     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

图的最大亏格与图的顶点划分

本文研究了图的Betti亏数与图的顶点划分的导出子图之间的关系,得到了图的最大亏格上界由其顶点划分的导出子图所表达的关系式,由此给出了图的最大亏格的一些新结果．     

Facial Nonrepetitive Vertex Coloring of Plane Graphs

A sequence is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G.     

一些图的邻点可区别关联着色

在图的关联着色概念的基础上定义了图的邻点可区别关联着色及邻点可区别关联色数,研究了圈、完全二部图、Cm.Fn图的邻点可区别关联着色,并确定了它们的邻点可区别关联色数.     

Additive Coloring of Planar Graphs

An additive coloring of a graph G is an assignment of positive integers \({\{1,2,\ldots ,k\}}\) to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by \({\eta (G)}\) . We prove that \({\eta (G) \, \leqslant \, 468}\) for every planar graph G. This improves a previous bound \({\eta (G) \, \leqslant \, 5544}\) due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that \({\eta (G) \, \leqslant \, 36}\) for 3-colorable planar graphs, and \({\eta (G) \, \leqslant \, 4}\) for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each \({r \, \geqslant \, 2}\) there is an r-chromatic graph G _r with no additive coloring by elements of any abelian group of order r.