首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 125 毫秒
1.
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.  相似文献   

2.
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.  相似文献   

3.
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.  相似文献   

4.
Let G be a simple graph. A total coloring f of G is called 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 E-total-coloring f of a graph G and any vertex u of G, let Cf (u) or C(u) denote the set of colors of vertex u and the edges incident to u. We call C(u) the color set of u. 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 colorings of G is denoted by X^evt(G), and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.  相似文献   

5.
The geodetic numbers of graphs and digraphs   总被引:1,自引:0,他引:1  
For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.  相似文献   

6.
《数学季刊》2016,(2):147-154
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.  相似文献   

7.
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 χievt(G), and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.  相似文献   

8.
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.  相似文献   

9.
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.  相似文献   

10.
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.  相似文献   

11.
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}.  相似文献   

12.
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)}.  相似文献   

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

14.
设$\varphi$为群${\rm Aut}(N)$的同态,记$H_\varphi\times N$为群$N$借助于群$H$的半直积.设$G$为有限不可解群,本文证明: 若$G$中最高阶元素个数为40, 则$G$同构于下列群之一:(1)~$Z_{4\varphi}\times A_5$,\,${\rm ker}\varphi=Z_2$; (2)~$D_{8\varphi}\times A_5,\,{\rm ker}\varphi=Z_2\times Z_2$; (3)~$G/N=S_5$, $N=Z(G)=Z_2$; (4)~$G/N=S_5$, $N=Z_2\times Z_2,\,N\cap Z(G)=Z_2$.  相似文献   

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

16.
设$D$是一个非平凡的对称$(v,k,\lambda)$设计, $G$是$D$的一个自同构群.本文证明了如果$G$以二维典型群PSL$(2,q)$作为基柱且在$D$上的作用是旗传递和点本原的,那么设计$D$的参数只能为$(7, 3, 1)$, $(7, 4, 2)$, $(11, 5, 2)$, $(11, 6, 3)$或$(15, 8, 4)$.  相似文献   

17.
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).  相似文献   

18.
确定了广义超特殊p-群G的自同构群的结构.设|G|=p~(2n+m),|■G|=p~m,其中n≥1,m≥2,Aut_fG是AutG中平凡地作用在Frat G上的元素形成的正规子群,则(1)当G的幂指数是p~m时,(i)如果p是奇素数,那么AutG/AutfG≌Z_((p-1)p~(m-2)),并且AutfG/InnG≌Sp(2n,p)×Zp.(ii)如果p=2,那么AutG=Aut_fG(若m=2)或者AutG/AutfG≌Z_(2~(m-3))×Z_2(若m≥3),并且AutfG/InnG≌Sp(2n,2)×Z_2.(2)当G的幂指数是p~(m+1)时,(i)如果p是奇素数,那么AutG=〈θ〉■Aut_fG,其中θ的阶是(p-1)p~(m-1),且Aut_f G/Inn G≌K■Sp(2n-2,p),其中K是p~(2n-1)阶超特殊p-群.(ii)如果p=2,那么AutG=〈θ_1,θ_2〉■Aut_fG,其中〈θ_1,θ_2〉=〈θ_1〉×〈θ_2〉≌Z_(2~(m-2))×Z_2,并且Aut_fG/Inn G≌K×Sp(2n-2,2),其中K是2~(2n-1)阶初等Abel 2-群.特别地,当n=1时...  相似文献   

19.
关于图的星色数的一点注记   总被引:1,自引:0,他引:1  
A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored.The star chromatic number of an undirected graph G,denoted by χs(G),is the smallest integer k for which G admits a star coloring with k colors.In this paper,we show that if G is a graph with maximum degree △,then χs(G) ≤ [7△3/2],which gets better bound than those of Fertin,Raspaud and Reed.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号