首页   按字顺浏览 期刊浏览 卷期浏览 A CARTESIAN REPRESENTATION OF A GRAPH
A CARTESIAN REPRESENTATION OF A GRAPH

 

作者: PA Winter,  

 

期刊: Quaestiones Mathematicae  (Taylor Available online 1988)
卷期: Volume 12, issue 1  

页码: 51-64

 

ISSN:1607-3606

 

年代: 1988

 

DOI:10.1080/16073606.1988.9632164

 

出版商: Taylor & Francis Group

 

关键词: 05C75

 

数据来源: Taylor

 

摘要:

IfGis a graph of order p and size q, we associate with each vertexvεGthe pair(d(v)—σ, Δ—d(v))which we call the coordinate (representation) ofvinG.The Cartesian graph ofG, denoted by cart(G), is defined as{(d(v)—σ,Δ- d(v)) | vε V}. The coordinate (a,a) of a vertex ofGis said to be simple inGwhile non-simple coordinate representations (a, b), (b, a) of vertices ofGform a mirror coordinate pair ofG.We characterise graphs for whichcart(G)=cart(G)and call such graphs Cartesian perfect. The Cartesian number of a graphG, denoted byxcart(G), is the sum of (i) the number of mirror coordinate pairs in a maximum setSof mirror coordinate pairs ofGand (ii) either 1 or 0 depending on whethercart(G)has a simple coordinate or not, respectively and (iii) the number of distinct non-simple coordinate representations of vertices ofGwhich do not belong to any mirror coordinate pair inS.GraphsGfor whichXcart(G)= x(G) are considered and we characterise k-Cartesian critical graphs (connected graphsGwith Xcart(G) =kandxcart(H) > kfor each connected subgraphHofG)for k=1,2 and 3. With each nonregular graphGwe associate the equationy =—x +Δ—σwhich we call the linear equation ofGwith intercept p = Δ—σ. A graphGis said to be (r)-linear with respect to its intercept p if (-p+r,q) satisfies its linear equation. For r ≥ 0 we characterise those Cartesian perfect graphsGfor which bothGand Ǥ are (r)-linear with respect to their interceptsp.

 

点击下载:  PDF (448KB)



返 回