Neighbor sum distinguishing total colorings of K 4-minor free graphs

A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv E E（G）, f（u） ≠ f（v）. By tt [G, Xsd（ J, we denote the smallest value k in such a coloring of G. Pilniak and Woniak conjectured X＇sd（G） 〈 A（G） ＋ 3 for any simple graph with maximum degree A（G）. This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for Ka-minor free graphs. Furthermore, we show that if G is a Ka-minor flee graph with A（G） 〉 4, then ＂ Xnsd（G） 〈 A（G） ＋ 2. The bound A（G） ＋ 2 is sharp.     

Longest Cycles in 3-Connected k-Regular Claw-Free Graphs

All graphs considered here are undirected aud finite without loop or multipleedges. A graph is called claw-free if it do not contain a K_(1,3) as an inducedsubgraph. Let δ(G) denote the minimum degree of a graph G, and let V(G) andE(G) be the vertex set and edge set of G, respectively. For a subset S of V(G)and a subgraph H of G,G[S] and G-H denote the subgraphs of G induced by the     

二部图的E-H-不可收缩性

By End（G） and hEnd（G） we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End（G） = hEnd（G）. A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly.     

Some properties for the largest component of random geometric graphs with applications in sensor networks

In this paper we consider the standard Poisson Boolean model of random geometric graphs G（Hλ,s; 1） in Rd and study the properties of the order of the largest component L1 （G（Hλ,s; 1）） . We prove that ElL1 （G（Hλ,s; 1））] is smooth with respect to A, and is derivable with respect to s. Also, we give the expression of these derivatives. These studies provide some new methods for the theory of the largest component of finite random geometric graphs （not asymptotic graphs as s - co） in the high dimensional space （d 〉 2）. Moreover, we investigate the convergence rate of E[L1（G（Hλ,s; 1））]. These results have significance for theory development of random geometric graphs and its practical application. Using our theories, we construct and solve a new optimal energy-efficient topology control model of wireless sensor networks, which has the significance of theoretical foundation and guidance for the design of network layout.     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G = （V, E） be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is N[S] = V. The domination number of G, denoted by γ（G）, is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number, denoted by γpr（G）, is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules： （i） all vertices in N[S] are observed initially, and （ii） if an observed vertex u has all neighbors observed except one neighbor v, then v is observed （by u）. The power domination number, denoted by γp（G）, is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively.     

具有5n个点的完全5部图的分类及5图部的色性

§ 1　IntroductionAll graphs considered here are finite and simple.For notations and terminology notdefined here,we refer to [1].For a graph G,by V(G) and E(G) we mean the vertex- setand edge- setof G,respectively.By N3(G) we denote the number of triangles in G.L et S bea set of sedges in G.By G- S (or G- s) we denote the graph obtained from G by deletingall edges in S.L et K (n1 ,n2 ,...,nt) be a complete t- partite graph.We denote by K- sn1 ,n2 ,...,ntthe family of graphs which are …     

Hamiltonian Cycles in 3-connected Claw-Free Graphs

All graphs considered in this paper are undirected and finite,without loops or mu-Itiple edges. A graph is called claw-free if it does not contain a copy of K_(1,3) as aninduced subgraph. For a subgraph H of G, G-H denotes the induced subgraph of byV(G)-V(H). If K and L are subsets or subgraphs, we denote by N_K(L) the set ofvertices in K which are adjacent to some vertex in L. In recent years there nave beena great many papers dealing with hamiltonian cycles in claw-free graphs. M.M.Matt-     

σ-多项式的根

§ 1　IntroductionAll graphs considered are finite and simple.Undefined notation and terminology willconform to those in[1 ] .Let V(G) ,E(G) and Gdenote the vertex set,edge set and complement of a graph G,respectively. Let P(G,x) andσ(G,x) denote the chromatic polynomial andσ-polynomialof G,respectively.The log-concavity property of the chromatic polynomial andσ-polyno-mial of G has a close relation to their roots,which were well studied in[2 ,3] .Results onthe study of the roots of…     

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.     

关于图符号的边控制 (英)

设γ's(G)和γ'ι(G)分别表示图G的符号边和局部符号边控制数,本文主要证明了:对任何n阶图G(n≥4),均有γ's(G)≤[11/6n-1]和γ'ι(G)≤2n-4成立,并提出了若干问题和猜想．     

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

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.     

On Centralizer Subalgebras of Group Algebras

Let $G$ be a finite group, $H ≤ G$ and $R$ be a commutative ring with an identity $1_R$. Let $C_{RG}(H) = \{ α ∈ RG|αh= hα$ for all $h ∈ H \}$, which is called the centralizer subalgebra of $H$ in $RG$. Obviously, if $H = G$ then $C_{RG}(H)$ is just the central subalgebra $Z(RG)$ of $RG$. In this note, we show that the set of all $H$-conjugacy class sums of $G$ forms an $R$-basis of $C_{RG}(H)$. Furthermore, let $N$ be a normal subgroup of $G$ and $γ$ the natural epimorphism from $G$ to $\overline{G}= G/N$. Then $γ$ induces an epimorphism from $RG$ to $R\overline{G}$, also denoted by $γ$. We also show that if $R$ is a field of characteristic zero, then $γ$ induces an epimorphism from $C_{RG}(H)$ to $C_{R\overline{G}}(\overline{H})$, that is, $γ(C_{RG}(H)) = C_{R\overline{G}}(\overline{H})$.     

完全$r$部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).本文证明对于一个完全γ部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立.作为一个推论,当G和H均为完全γ部图时,Graham猜想成立.     

$p$-子群具有$p$-超可解正规化子的有限群

在已有研究中,对于$p$-子群的正规化子而言,它的$p$-幂零性质对有限$p$-幂零群的结构具有重要的影响. 本文中, 设$P$是群$G$的西罗$p$-子群, $1\leq p^d<|P|$, 对于$P$的每个阶为$p^d$的正规子群$H$H,将$N_G(H)$的$p$-幂零性质减弱为$p$-超可解性质,结合$H$的弱$M$-可补充性质,探究$p$-超可解群的结构.同时,在$N_G(P)$是$p$-幂零的条件下,利用子群$K$的弱$M$-可补充条件研究群的$p$-幂零性质,其中$K_p\leq K$且$P''\leq K_p\leq \Phi(P)$. $K_p$是$K$的西罗$p$-子群.在一定程度上,主要结果推广了Frobenius定理.     

半无爪可迹图的度和条件

可迹图即为一个含有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}$,则该图为可迹图.     

最大度与最小度相差不超过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.     

L7（3）与GL7（3）的OD-刻画

对于任意一个有限群G,令π（G）表示由它的阶的所有素因子构成的集合.构建一种与之相关的简单图,称之为素图,记作Γ（G）.该图的顶点集合是π（G）,图中两顶点p,g相连（记作p～q）的充要条件是群G恰有pq阶元.设π（G）={P₁,p2,…,p_x}.对于任意给定的p∈π（G）,令deg（p）:=|{q∈π（G）|在素图Γ（G）中,p～q}|,并称之为顶点p的度数.同时,定义D（G）:=（deg（p₁）,deg（p₂）,…,deg（p_s））,其中p₁2<…相似文献   

一个关于平面图的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$.     

单圈图的极小能量

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un| d(x) = r for any vertex x ∈ V(Cl)}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39(2, 2, 2) ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.