A CARTESIAN REPRESENTATION OF A GRAPH

Abstract

If G is a graph of order p and size q, we associate with each vertex v ε G the pair (d(v)—σ, Δ—d(v)) which we call the coordinate (representation) of v in G. The Cartesian graph of G, denoted by cart(G), is defined as {(d(v)—σ,Δ- d(v)) | v ε V}. The coordinate (a,a) of a vertex of G is said to be simple in G while non-simple coordinate representations (a, b), (b, a) of vertices of G form a mirror coordinate pair of G. We characterise graphs for which cart(G) = cart(G) and call such graphs Cartesian perfect. The Cartesian number of a graph G, denoted by x_cart (G), is the sum of (i) the number of mirror coordinate pairs in a maximum set S of mirror coordinate pairs of G and (ii) either 1 or 0 depending on whether cart(G) has a simple coordinate or not, respectively and (iii) the number of distinct non-simple coordinate representations of vertices of G which do not belong to any mirror coordinate pair in S. Graphs G for which X_cart(G) = x(G) are considered and we characterise k-Cartesian critical graphs (connected graphs G with X_cart (G) = k and x_cart (H) > k for each connected subgraph H of G) for k=1,2 and 3. With each nonregular graph G we associate the equation y =—x +Δ—σ which we call the linear equation of G with intercept p = Δ—σ. A graph G is 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 graphs G for which both G and [Gbar] are (r)-linear with respect to their intercepts p.

1980 AMS Subject Classification:

• 05C75