L（1, 2）-edge-labelings for lattices

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0, 1, 2,..., m}, such that adjacent edges which receive labels differ at least by j, and edges which are distance two apart receive labels differ at least by kThe λ j,k-number of G is the minimum m such that an m-L(j, k)-edge-labeling is admitted by GIn this article, the L(1, 2)-edge-labeling for the hexagonal lattice, the square lattice and the triangular lattice are studied, and the bounds for λ j,k-numbers of these graphs are obtained.     

完全图的Cantesian积的L(2,1)-圆标定

For positive integers j and k with j ≥ k, an L（j, k）-labeling of a graph G is an assignment of nonnegative integers to V（G） such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L（j, k）-labeling of a graph G is the difference between the maximum and minimum integers it uses. The λj, k-number of G is the minimum span taken over all L（j, k）-labelings of G. An m-（j, k）-circular labeling of a graph G is a function f ： V（G） →{0, 1, 2,..., m - 1} such that ｜f（u） - f（v）｜m ≥ j if u and v are adjacent; and ｜f（u） - f（v）｜m 〉 k ifu and v are at distance two, where ｜x｜m = min{｜xl｜, m-｜x｜}. The minimum integer m such that there exists an m-（j, k）-circular labeling of G is called the σj,k-number of G and is denoted by σj,k（G）. This paper determines the σ2,1-number of the Cartesian product of any three complete graphs.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

Edge coloring by total labelings of outerplanar graphs

An edge coloring totalk-labeling is a labeling of the vertices and the edges of a graph G with labels{1,2,...,k}such that the weights of the edges defne a proper edge coloring of G.Here the weight of an edge is the sum of its label and the labels of its two end vertices.This concept was introduce by Brandt et al.They defnedχt(G)to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question:Is there a constant K withχt(G)≤Δ(G)+12+K for all graphs G of maximum degreeΔ(G)?In this paper,we give a positive answer for outerplanar graphs by showing thatχt(G)≤Δ(G)+12+1 for each outerplanar graph G with maximum degreeΔ(G).     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

THE ENUMERATION OF SELF-COMPLEMENTARY k-MULTIGRAPHS

1. IntroductionThe graphs considered in this paper are multigraphs, i.e., every pair of venices in agraph can be joined by two or more edges. A graph G is called the k-multigraph if every pairof venices in G can be joined by at most k edges (k≥2). The complete k-multigraph withp vertices, denoted by K, is the multigraph in which every pair of venices is exactly joinedby k edges. The complement of a k-multigraph G, denoted by G, is a k-multigraph in whichV(G) = V(G); and for each pair of v…     

Number of Induced Matchings of Graphs

A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.     

恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

关于图的3-条件色数

For integers k0,r0,a(k,r)-coloring of a graph G is a proper k-coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min{d,r}diferent colors.The r-hued chromatic number,denoted byχr(G),is the smallest integer k for which a graph G has a(k,r)-coloring.Define a graph G is r-normal,ifχr(G)=χ(G).In this paper,we present two sufcient conditions for a graph to be 3-normal,and the best upper bound of 3-hued chromatic number of a certain families of graphs.     

关于完全三部图色唯一性的一个注记

Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.     

一类完全多部图的色可选择性

如果一个图G的选择数等于它的色数,则称该图G是色可选择的．在2002年, Ohba给出如下猜想:每一个顶点个数小于等于2X(G) 1的图G是色可选择的．容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba猜想的正确性．在本文我们证明图K6,3,2*(k-6),1*4(k≥6)是色可选择的,从而对图K6,3,2*(k-6),1*4(k≥6)和它们的所有完全k-部子图证明了Ohba猜想成立．     

图的平面Turán数和平面anti-Ramsey数

在所有顶点数为$n$且不包含图$G$作为子图的平面图中,具有最多边数的图的边数称为图$G$的平面Turán数,记为$ex_{_\mathcal{P}}（n,G）$。给定正整数$n$以及平面图$H$,用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$,则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数,记作$ar_{_\mathcal{P}}（n,H）$。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.