Longest Paths and Cycles in Connected Claw-Free Graphs

A graph is called claw-free if it does not contain a claw as its induced subgraph. In this paper, we prove the following results : 1 ) If G is a 2-connected claw-free graph on n vertices, then for any vertex υ and any two distinct vertices x and y in V(G) - |υ| , G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G - C,and if H is connected but not 2-connected, then there exist nonadjacent vertices u and v in H such that |V(C)| ≥3(d(u) d(u)) -2.     

图的符号全划分数

Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs.     

A Note on Vulnerability in Graphs of Diameter Five(Ⅱ)

1IntroductionIn general,we followthe notation and terminologyin Refs.[1-5,7].In this paper all graphs are si mple.LetGbe a graph,V(G)the vertex set ofG,andE(G)the edge set ofG.The distance between twoverticesx,y∈V(G)is denoted bydG(x,y).Thediameter ofGis denoted byd(G).A short(x,y)-pathis an(x,y)-path with length≤d(G).An edgee∈E(G)is called cyclic if there exists a cycle inGcontaininge.To each cyclic edgee,letg(e)be thelength of the shortest cycle containinge.Ifeis abridge theng(e)…     

Symmetry properties of tetraammine platinum（Ⅱ） with C2v and C4v point groups

Let G be a weighted graph with adjacency matrix A=[aij]. An Euclidean graph associated with a molecule is defined by a weighted graph with adjacency matrix D=[d/ij], where for i≠j, dij is the Euclidean distance between the nuclei i and j. In this matrix dij can be taken as zero if all the nuclei are equivalent. Otherwise, one may introduce different weights for different nuclei.Balasubramanian (1995) computed the Euclidean graphs and their automorphism groups for benzene, eclipsed and staggered forms of ethane and eclipsed and staggered forms of ferroeene. This paper describes a simple method, by means of which it is possible to calculate the automorphism group of weighted graphs. We apply this method to compute the symmetry of tetraammine platinum(Ⅱ) with C2v and C4v point groups.     

Minus total κ-subdomination in graphs

Let G=(V, E)be a simple graph without isolated vertices. For positive integer κ, a 3-valued function f:V → {-1, 0, 1} is said to be a minus total k-subdominating function(MTκSF)if ∑u∈N(u)f(u)≥ 1 for at least κ vertices v in G, where N(v)is the open neighborhood of v. The minus total κ-subdomination number γ-κt(G)equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total κ-subdomination number of some special graphs are investigated. Several lower bounds on γ-κt of general graphs and trees are obtained.     

Using the Wavelet as the Private Key for Encrypting the Watermark

Watermarking is an effective approach to the copyright protection of digital media such as audio,image,and video.By inspriation from cryptography and considering the immensity of the set of all possible wvaelets,it is presented that in wavelet domain watermarking,the associated wavelet can be considered as the private key for encrypting the wavtermark so as to enhance the security of the embedded mark.This idea is partly supported by the fact that from computational complexity viewpoint.It is very time-consuming to search over the immense set of all candidate wavelets for the right one if no a priori knowledge is known about it .To verify our proposal,the standard image“Lena”is first watermarked in a specific wavelet domain,the watermark recovery experiments are then conducted in the wavelet domain for a set of wavelets with the one used for mark embedded in it ,separately.It follows from the experimetal results that the mark can be recovered only in the right wavelet domain,which jusstifies the suggestion.     

图的整数值控制函数

For an arbitrary subset P of the reals, a function f ： V →P is defined to be a P-dominating function of a graph G = （V, E） if the sum of its function values over any closed neighbourhood is at least 1. That is, for every v ∈ V, f（N[v]） ≥ 1. The definition of total P-dominating function is obtained by simply changing ‘closed＇ neighborhood N[v] in the definition of P-dominating function to ‘open＇ neighborhood N（v）. The （total） P-domination number of a graph G is defined to be the infimum of weight w（f） = ∑v ∈ V f（v） taken over all （total） P-dominating function f. Similarly, the P-edge and P-star dominating functions can be defined. In this paper we survey some recent progress on the topic of dominating functions in graph theory. Especially, we are interested in P-, P-edge and P-star dominating functions of graphs with integer values.     

Definition of an Ellipse

If F1 （c, 0） and F2（ -c, 0） are two fixed points in the plane and a is a constant, 0〈c〈a, then the set of all points P in the plane such that ｜ PF1｜ ＋ ｜ PF2 ｜ = 2a is an ellipse. F1 and F2 are the loci of the ellipse.     

图的整数值控制函数

For an arbitrary subset P of the reals,a function f:V→P is defined to be a P-dominating function of a graph G=(V,E) if the sum of its function values over any closed neighbourhood is at least 1.That is,for every v∈V, f(N[v])≥1.The definition of total P-dominating function is obtained by simply changing‘closed’neighborhood N[v]in the definition of P-dominating function to‘open’neighborhood N(v).The (total) P-domination number of a graph G is defined to be the infimum of weight w(f) =∑_(v∈V)f(v) taken over all (total) P-dominating function f.Similarly,the P-edge and P-star dominating functions can be defined.In this paper we survey some recent progress oil the topic of dominating functions in graph theory.Especially,we are interested in P-,P-edge and P-star dominating functions of graphs with integer values.     

Definition of the Hyperbola

A hyperbola is the set of all points P（x,y） in the plane such that ｜PF1 - PF2｜ = 2a. Again F1 and F2 are focus points. This time the difference of these distances remain a constant at 2a. The explanation is similar to that of the ellipse. Since the ellipse is the sum of the distances and the hyperbola is the difference of the distances, the equations are very similar. They differ on- ly in the sign and the longest side for a hyperbola is c. （Remember for the ellipse it was a ）     

一种构造k-色临界图的方法

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。     

一类含有两个分支2-因子的无爪图

文章主要证明了若图G是阶为n,n>9的连通无爪图,G中至少存在一个非局部连通点或一个单纯点,M(G)={x|x∈V(G),x局部连通}是G的一个连通控制集,则G含有两个分支的2-因子。     

路和圈的边冠图的路分解

边冠图G□H是由图G和H合成的图,其中使图G的每条边的两端点与图H的一个拷贝的所有顶点相连.如果图G的边集合可以分解为若干个边不相交的子图H,那么称G有子图H的分解,当H是P3或P4时,就称G有{P3,P4}分解.本文讨论了一些边冠图的{P3,P4}分解问题,即:边冠图Pm□Pn、Pm□Cn、Cm□Pn及Cm□Cn存在{P3,P4}分解.     

关于双图的群染色（英文）

若图G=（V,E）,给定方向为D,A表示一个非平凡的阿贝尔群,F（G,A）表示映射f：E（G）→A的集合.若对任意f∈F（G,A）存在映射c：V（G）→A,使得G中的每一条有向边e=uv∈E（G）（方向是u→v）满足c（u）-c（v）≠f（e）,这时说图G是A-可染的.使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg（G）.主要是在分析了一些双图的特性的基础上讨论了它们的群色数.对于任意阶路的双图可得出其群色数都是3,还证明了圈的双图的群色数不超过5以及得到其它一些双图的群色数的上界.     

关于整和图的几个新结果

若图G的顶点可以用一个关于不同整数的标号函数f给出,使得对于G的任意两个不同的顶点u 和v,uv 是G 的边当且仅当f(u) + f(v) =f(w),w为G 的某个顶点,则图G称为整和图(integral sum graph).现给出完全三部图K1,1,r r≥3的(整)和数、完全三部图K1,r,r r≥2(整)和数的一个上下界,并证明了扇图 Fn 及任意个扇图在中心处相交构成的图是整和图,同时得到荷兰风车Dn 也是整和图.     

平衡二部图的孤立断裂度

连通图G的孤立断裂度定义为isc（G）=max{i（G-S）-｜S｜：S∈C（G）},其中i（G-S）是G-S中的孤立点数,C（G）是G的点割集。本文给出了平衡二部图的孤立断裂度以及图的孤立断裂度与图的哈密顿性的关系。     

k-路的零度

图G的零度,记为η(G),是指图的邻接谱中零特征值的重数.若一个图既是k-树也是区间图,则称这个图为k-路,记n个顶点的k-路为Pnk.通过对Pkn奇异性的研究证明了Pn2是拟非奇异图.     

广义Mycielski图的D(β)-点可区别VIE-全染色

单图G的D(β)-点可区VIE-全染色是满足当u,v∈V(G),0相似文献   

围长较大的平面图的全染色的一个结果

图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ＂（G）为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ（G）＋2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ（G）＋1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ（G）＋1.