共查询到20条相似文献,搜索用时 631 毫秒
1.
2.
3.
关于图的色多项式的若干问题 总被引:4,自引:0,他引:4
<正> 设G是连通的无向的标定的(p,q)图.集S={1,2,…,t}.G的一个t-着色σ是G的点的集V(G)到S内的一个映射,满足条件:若u,v∈V(G)在G中邻接,则σu≠σv.G的不同的t-着色的总数f(G;t)是t的一个p次多项式.(关于色多项式的一般论述,下文未注明出处的结果及未给出定义的名词与记号均参见[1]).这个多项式记作 相似文献
4.
给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性. 相似文献
5.
6.
7.
路与完全图的笛卡尔积图和广义图K(n,m)的关联色数 总被引:4,自引:0,他引:4
Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数. 相似文献
8.
9.
10.
第一类图的若干充分性条件 总被引:7,自引:0,他引:7
1964年,V.G.Vizing[2]证明了简单图 G 的边色数 x′(G)满足△(G)≤x′(G)≤△(G)+1.其中△(G)为图 G 的最大度.若x′(G)=△(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=△(G)+1 则称 G 为第二类图,并简记为 G∈C~2. 相似文献
11.
On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number 下载免费PDF全文
Xiao Ming Pi 《数学学报(英文版)》2018,34(5):911-920
Let G =(V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function(SCDF) of G if ∑_(e∈E(C))f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ'_(sc)(G) = min{∑_(e∈E)f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ'_(sc)(G) = n. 相似文献
12.
Margaret B. Cozzens
Mark D. Halsey
《Discrete Applied Mathematics》1991,30(2-3):125-135Let the coboxicity of a graph G be denoted by cob(G), and the threshold dimension by t(G). For fixed k≥3, determining if cob(G)≥k and t(G)≤k are both NP-complete problems. We show that if G is a comparability graph, then we can determine if cob(G)≤2 in polynomial time. This result shows that it is possible to determine if the interval dimension of a poset equals 2 in polynomial time. If the clique covering number of G is 2, we show that one can determine if t(G)≤2 in polynomial time. Sufficient conditions on G are given for cob(G)≤2 and for t(G)≤2. 相似文献
13.
A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R>0. The weighted domination number γw(G) of (G,w) is the minimum weight w(D)=∑vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved thatfor normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement
has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs. 相似文献
14.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph Jk(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2(G) is planar are determined. 相似文献
15.
Byeong Moon Kim Byung Chul Song Woonjae Hwang 《Linear algebra and its applications》2007,420(2-3):648-662
A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even. 相似文献
16.
Let G be a finite connected graph. The eccentric connectivity index ξc(G) of G is defined as ξc(G)= v∈V (G) ec(v)deg(v), where ec(v) and deg(v) denote the eccentricity and degree of a vertex v in G, respectively. In this paper, we give an asymptotically sharp upper bound on the eccentric connectivity index in terms of order and vertex-connectivity and in terms of order and edge-connectivity. We also improve the bounds for triangle-free graphs. 相似文献
17.
18.
The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases. 相似文献
19.
Hong-Jian Lai 《Discrete Mathematics》2001,230(1-3):63-69
For an integer l0, define
to be the family of graphs such that
if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in
are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in
. Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended. 相似文献
20.
Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288] that G admits an acyclic coloring with O(Δ4/3) colors and a proper coloring with O(Δ(k−1)/(k−2)) colors such that no path with k vertices is bichromatic for a fixed integer k≥5. In this paper, we combine above two colorings and show that if k≥5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ(k−1)/(k−2)) colors such that no path with k vertices is bichromatic. 相似文献