Prime Graphs with Almost True Twin Vertices
Prime Graphs with Almost True Twin Vertices
A graph G consists of a possibly infinite set V(G) of vertices with a collection E(G) of unordered pairs of distinct vertices, called the set of edges of G. Such a graph is denoted by (V(G),E(G)). Two distinct vertices u and v of a graph G are adjacent if {u,v}is an element of E(G). Let G be a graph. A subset M of V(G) is a module of G if every vertex outside M is adjacent to all or none of the vertices in M. The graph G is prime if it has at least four vertices, and its only modules are & empty;, the single-vertex sets, and V(G). Given two adjacent vertices u and v of G, v is a negative almost true twin of u in G if there is a vertex xv in V(G)\{u} non-adjacent to u such that the pair {u,v} is a module of the graph (V(G),E(G)boolean OR{{u,xv}}). In this paper, we study graphs with a negative almost true twin for a given vertex, and we give some applications. Firstly, we characterize these graphs by a special decomposition, and we specify the prime graphs among them. Secondly, we give three applications, giving methods for extending graphs to prime graphs. Finally, we study the prime induced subgraphs of the prime graphs with at least two negative almost true twins for a given vertex.
A graph G consists of a possibly infinite set V(G) of vertices with a collection E(G) of unordered pairs of distinct vertices, called the set of edges of G. Such a graph is denoted by (V(G),E(G…