| Автор | Winter, P A |
| Дата выпуска | 1988 |
| dc.description | AbstractIf 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<sub>cart</sub> (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<sub>cart</sub>(G) = x(G) are considered and we characterise k-Cartesian critical graphs (connected graphs G with X<sub>cart</sub> (G) = k and x<sub>cart</sub> (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. |
| Формат | application.pdf |
| Издатель | Taylor & Francis Group |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | 05C75 |
| Название | A CARTESIAN REPRESENTATION OF A GRAPH |
| Тип | research-article |
| DOI | 10.1080/16073606.1988.9632164 |
| Electronic ISSN | 1727-933X |
| Print ISSN | 1607-3606 |
| Журнал | Quaestiones Mathematicae |
| Том | 12 |
| Первая страница | 51 |
| Последняя страница | 64 |
| Аффилиация | Winter, P A; Department of Mathematics and Applied Mathematics, University of Natal |
| Выпуск | 1 |
| Библиографическая ссылка | Behzad, M, Chartrand, G and Lesniak-Forster, L. 1979. Graphs and Digraphs. Monterey: Wadsworth. |
| Библиографическая ссылка | Fiorini, S and Wilson, R J. 1977. Edge-colourings of graphs. London: Pitman. |
