Article ID Journal Published Year Pages File Type
9513250 Discrete Mathematics 2005 7 Pages PDF
Abstract
The first part of this paper deals with the properties of C3-saturated graphs. It will be shown that for any C3-saturated graph, G, D2(D2(G))=G, where Dk(G) is the graph with vertex set V(G), with which two vertices are adjacent iff the distance between them, in G, is k. In addition to this, a full description of the set of planar C3-saturated graphs, PSAT(n,C3), will be given. It will be shown that there are only three kinds of such graphs. In the second part of the paper a useful characterization of graphs which are C3-saturated and C4-free will be given in terms of the adjacency and incidence matrices A and B.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,