Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥_n-factor if its each component admits at least n vertices. A graph G is called P≥_n-factor covered if G admits a P≥_n-factor containing e for any e ∈ E(G), which is defined by[Discrete Mathematics, 309, 2067–2076(2009)]. We first define the concept of a(P≥_n, k)-factor-critical covered graph, namely, a graph G is called(P≥_n, k)-factor-critical covered if G-D is P≥_n-factor covered for any D ? V(G) with |D| = k. In this paper, we verify that(i) a graph G with κ(G) ≥ k + 1 is(P≥2, k)-factor-critical covered if bind(G) 2+k/3;(ii) a graph G with |V(G)| ≥ k + 3 and κ(G) ≥ k + 1 is(P≥3, k)-factor-critical covered if bind(G) ≥4+k/3.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

On k-critical 2k-connected graphs

A graph G is called an (n, k)-graph if k(G - S) = n - |S| for any S V(G) with |S| ≤ k, where k.(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K2k+2 - (1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3, 4. We prove the conjecture for the general case k ≥ 5.     

Exact Solution to an Extremal Problem on Graphic Sequences with a Realization Containing Every 2-Tree on k Vertices

A simple graph G is a 2-tree if G=K_3,or G has a vertex v of degree 2,whose neighbors are adjacent,and G-v is a 2-tree.Clearly,if G is a 2-tree on n vertices,then |E(G)|=2 n-3.A non-increasing sequence π=(d_1,...,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.[Acta Math.Sin.Engl.Ser.,25,795-802(2009)] proved that if k≥2,n≥9/2 k~2+19/2 k and π=(d_1,...,d_n) is a graphic sequence with∑_(i=1)~n di(k-2)n,then π has a realization containing every 1-tree(the usual tree) on k vertices.Moreover,the lower bound(k-2)_n is the best possible.This is a variation of a conjecture due to Erdos and Sos.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] ~2+31[k/3]+12 and π=(d_1,...,d_n) is a graphic sequence with ∑_(i=1)~n d_imax{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].     

Path Factors and Neighborhoods of Independent Sets in Graphs

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_≥k-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_≥k-factor covered graph if for any e∈E(G),G has a P_≥k-factor including e.Let β be a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ) a k-connected graph G of order n with n≥5k+2 has a P_≥3...     

Graphic sequences with a realization containing intersecting cliques

Let r≥ 1, k≥ 2 and Fm1 ,...,mki;r denote the most general definition of a friendship graph, that is, the graph of Kr+m1 , . . . , Kr+mk meeting in a common r set, where Kr+mi is the complete graph on r + mi vertices. Clearly, | Fm1 ,...,mki;r | = m1+ ··· + mk + r. Let σ(Fm1 ,...,mki;r , n) be the smallest even integer such that every n-term graphic sequence π = (d1, d2, . . . , dn) with term sum σ(π) = d1 + d2 + ··· + dn ≥σ(Fm1 ,...,mki;r,n) has a realization G containing Fm1 ,...,mki;r as a subgraph. In this paper, we determine σ(Fm1 ,...,mki;r,n) for n sufficiently large.     

The limit case of a domination property

The domination number γ(G) of a connected graph G of order n is bounded below by(n+2-e(G))/ 3 , where (G) denotes the maximum number of leaves in any spanning tree of G. We show that (n+2-e(G))/ 3 = γ(G) if and only if there exists a tree T ∈ T ( G) ∩ R such that n1(T ) = e(G), where n1(T ) denotes the number of leaves of T1, R denotes the family of all trees in which the distance between any two distinct leaves is congruent to 2 modulo 3, and T (G) denotes the set composed by the spanning trees of G. As a consequence of the study, we show that if (n+2-e(G))/ 3 = γ(G), then there exists a minimum dominating set in G whose induced subgraph is an independent set. Finally, we characterize all unicyclic graphs G for which equality (n+2-e(G))/ 3= γ(G) holds and we show that the length of the unique cycle of any unicyclic graph G with (n+2-e(G))/ 3= γ(G) belongs to {4} ∪ {3 , 6, 9, . . . }.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.     

一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

不含某些子图的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$ 可收缩边.     

完全图的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.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).     

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.