Some Structural Resuits on Prime Graphs
DOI:
https://doi.org/10.24297/jam.v17i0.8519Keywords:
Prime GraphsAbstract
Given a graph G = (V,E), a subset M of V is a module [17] (or an interval [10] or an autonomous [11] or a clan [8] or a homogeneous set [7] ) of G provided that x ∼ M for each vertex x outside M. So V,φ and {x}, where x ∈ V , are modules of G, called trivial modules. The graph G is indecomposable [16] if all the modules of G are trivial. Otherwise we say that G is decomposable . The prime graph G is an indecomposable graph with at least four vertices. Let G and H be two graphs. Let If G has no induced subgraph isomorphic to H, then we say that G is H-free. In this paper, we will prove the next theorem
Downloads
References
A. Ehrenfeucht, T. Harju and G. Rozenberg, The Theory of 2-Structures. A Framework for Decomposition and Transformation of Graphs, World Scientific, Singapore (1999).
I. Boudabbous and P. Ille, Critical and infinite directed graphs, Discrete Math. 307 (2007) 2415-2428.
Y. Boudabbous and P. Ille, Indecomposability graphs and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839-2846.
A. Brandst¨adt and D. Kratsch ,On the structure of (P5, gem)-free graphs, Discrete Applied Mathematics 145, (2005) 155-166.
M. Chudnovsky and P. Maceli, Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the H6-conjecture, Journal of Graph Theory, Vol 76, Issue 4, (2014) 249261.
M. Chudnovsky and P. Seymour, Growing without cloning, SIAM. Discrete Math., vol. 26, No. 2 (2012) 860-880.
A. Cournier and M. Habib, An efficient algorithm to recognize prime undirected graphs, in: Graph-Theoretic Concepts in Computer Science, Proceedings of the 18th Internat. Workshop, WG’92, Wiesbaden-Naurod, Germany, June 1992, in: E. W. Mayr(Ed.), Lecture Notes in Computer Science, Vol. 657, Springer, Berlin pp. 212-224 (1993).
A. Ehrenfeucht and G. Rozenberg, Primitivity is hereditary for 2-structures, fundamental study, Theoret. Comput. Sci. 3 (70), 343-358 (1990).
J.L . Fouquet, Adecompostion for a class of (P5,P5)-free graphs, Discrete Mathematics 121 ( 1993) 75-83.
R. Fra¨ıss´e, L’intervalleenth´eorie des relations, sesg´en´eralisations, filtreintervallaire et clˆotured’une relation, in: M. Pouzet and D. Richard eds., Order, Description and Roles, North-Holland, Amsterdam, (1984) 313- 342.
T. Gallai, TransitivorientierbareGraphen, Acta . Math. Acad. Sci. Hungar., 18 (1967) 25-66.
P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78.
P. Ille, A new proof of the main theorem of the paper: P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78, Homepage of Pierre Ille.
P. Ille, A characterization of the Indecomposable and Infinite Graphs, Glob. J. Pure Appl. Math. volume 1, Number 3, 272-285 (2005).
M. Pouzet and I. Zaguia, On minimal prime graphs and posets, Order Vol. 26 No. 4, (2009) 357-375.
J.H. Schmerl and W.T. Trotter, Critically indecomposable ordered sets, graphs, tournaments and other binary relation structures, Discrete Math. 113, 191-205 (1993).
J. Spinrad, P4-trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263-291.
D.P. Sumner, Graphs indecomposable with respect to X-join, Discrete Math. 6, (1973) 281-298.
Downloads
Published
How to Cite
Issue
Section
License
All articles published in Journal of Advances in Linguistics are licensed under a Creative Commons Attribution 4.0 International License.
