直径不超过4的树的割宽

§ 1　IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see [2 ] ) .We shall follow the graph-theoretic terminology and notation of [1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…     

Constructive characterizations of (γp,γ)- and (γp,γpr)-trees

Let G = (V,E) be a graph without isolated vertices.A set S 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 C 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 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.     

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

Let G =(V,E) be a graph without isolated vertices.A set S  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  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  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.     

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.     

σ-多项式的根

§ 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…     

The product of the restrained domination numbers of a graph and its complement

Let G=(V,E) be a graph.A set S■V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S.The restrained domination number of G,denoted γr(G),is the smallest cardinality of a restrained dominating set of G.In this paper,we show that if G is a graph of order n≥4,then γr(G)γr(G)≤2n.We also characterize the graphs achieving the upper bound.     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

符号混合控制问题的某些NP-完全性结果

Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.     

A conjecture on k-factor-critical and 3-γ-critical graphs

For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(resp.domination edge critical) and γ(G) = k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.     

Risk models for the Prize Collecting Steiner Tree problems with interval data

Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.     

图的割宽极值问题

The problem studied in this paper is to determine e(p, C), the minimum size of a connected graph G with given vertex number p and cut-width C.     

小度数循环图的计数

循环图已被用于平行计算，网络等方面．循环图研究的一个基本问题是对互不同构的循环图进行计数．对于给定的一个正整数ｎ，用Ｃ（ｎ，ｋ）表示互不同构的具有几个顶点，度数为ｋ的连通循环图的个数．文中给出了度数为 ４和５的循环图的一般结构，并对ｎ＝ｐａｑｂ（ｐ，ｑ皆为素数，ａ，ｂ＞０），给出了Ｃ（ｎ，４）的计算公式．     

关于带宽极值问题的两个结果

本文研究的问题是确定ｅ＊（ｐ,Ｂ）的值,也就是确定顶点数为ｐ、带宽为Ｂ的连通图Ｇ的最小边数,本文给出当Ｂ＝ｐ＋３／２和Ｂ＝ｐ／２＋２时的精确结果。     

关于带宽极值问题的一些结果

本文研究的问题是确定f(p,B）的值，也就是给定顶点数p和带宽B，求满足最大度不超过B的连通图的最小边数，本文给出了一些f(p,B）的值及相应极图。     

4p阶二面体群的弱3-CI性

决定了4p(p是奇素数)阶二面体群的连通3度Cayley图的完全分类,并证明4p阶二面体群不是弱3-CI群,从而否定了C.H.Li关于"所有有限群都是弱3-CI群"的猜想     

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) = (dij )n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a su?cient and necessary condition for complete r-partite graphs Kp1,p2,··· ,pr =Ka1·p1,a2·p2,··· ,as···ps to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs Ka1·p1,a2·p2,··· ,as·ps with s>4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with s = 5, 6. The problem of the existence of such distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with arbitrarily large number s remains open.     

Decomposition of two classes of structural models

The conditional independence structure of a common probability measure is a structural model. In this paper, we solve an open problem posed by Studeny [Probabilistic Conditional Independence Structures, Theme 9, p. 206]. A new approach is proposed to decompose a directed acyclic graph and its optimal properties are studied. We interpret this approach from the perspective of the decomposition of the corresponding conditional independence model and provide an algorithm for identifying the maximal prime subgraphs in a directed acyclic graph.     

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

p~2阶弧传递循环图的正规性条件

群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1.     

4p阶3度点传递图

一个图称为点传递图,如果它的全自同构群在它的顶点集合上作用传递.证明了一个4p(p为素数)阶连通3度点传递图或者是Cayley图,或者同构于下列之一;广义Petersen图P(10,2),正十二面体,Coxeter图,或广义Petersen图P(2p,k),这里k2≡-1(mod 2p).