Birecognition of prime graphs, and minimal prime graphs

被引:0
作者
Belkhechine, Houmem [1 ]
Ben Salha, Cherifa [2 ]
Ille, Pierre [3 ]
机构
[1] Univ Carthage, Bizerte Preparatory Engn Inst, Bizerte, Tunisia
[2] Univ Carthage, Fac Sci Bizerte, Bizerte, Tunisia
[3] Aix Marseille Univ, I2M, Cent Marseille, CNRS, Marseille, France
关键词
Module; prime graph; primality birecognition; minimal prime graph; RECOGNITION;
D O I
10.1142/S1793830922500380
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a graph G, a subset M of V (G) is a module of G if for each v is an element of V (G) set minus M, v is adjacent to all the elements of M or to none of them. For instance, V (G), null and {v} (v is an element of V (G)) are the trivial modules of G. A graph G is prime if |V (G)|>= 4 and all its modules are trivial. Given a prime graph G, consider X (sic) V (G) such that G[X] is prime. Given a graph H such that V (G) = V (H) and G[X] = H[X], G and H are G[X]-similar if for each W (sic) V (G) set minus X, G[X boolean OR W] and H[X boolean OR W] are both prime or not. The graph G is said to be G[X]-birecognizable if every graph, G[X]-similar to G, is prime. We study the graphs G that are not G[X]-birecognizable, where X (sic) V (G) such that G[X] is prime, by using the following notion of a minimal prime graph. Given a prime graph G, consider X (sic) V (G) such that G[X] is prime. Given v,w is an element of V (G) set minus X, G is G[X boolean OR{v,w}]-minimal if for each W (sic) V (G) such that X ?{v,w}subset of W, G[W] is not prime.
引用
收藏
页数:30
相关论文
共 11 条
[1]   Indecomposability graph and indecomposability recognition [J].
Boussairi, A. ;
Chaichaa, A. ;
Ille, P. .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 37 :32-42
[2]  
Breiner A., 2008, Contrib. Discrete Math., V3, P40
[3]   Minimal indecomposable graphs [J].
Cournier, A ;
Ille, P .
DISCRETE MATHEMATICS, 1998, 183 (1-3) :61-80
[4]  
Cournier A., 1993, Graph-Theoretic Concepts in Computer Science. 18th International Workshop, WG '92, P212
[5]  
Ehrenfeucht A, 1999, Theory Of 2-structures, the: a framework for decomposition and transformation of graphs
[6]   TRANSITIV ORIENTIERBARE GRAPHEN [J].
GALLAI, T .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2) :25-&
[7]   Recognition of prime graphs from a prime subgraph [J].
Ille, P. ;
Villemaire, R. .
DISCRETE MATHEMATICS, 2014, 327 :76-90
[8]  
ILLE P, 1993, NATO ADV SCI INST SE, V411, P189
[9]  
Maffray F, 2001, WIL INT S D, P25
[10]   P4-TREES AND SUBSTITUTION DECOMPOSITION [J].
SPINRAD, J .
DISCRETE APPLIED MATHEMATICS, 1992, 39 (03) :263-291