IJPAM: Volume 43, No. 3 (2008)

SPLIT-PSEUDOPATHS IN SPLIT-PRIME EXTENSIONS

S. Dubois$^1$, V. Giakoumakis$^2$, C.B. Ould El Mounir$^3$
$^{1,2,3}$Economics Business and Management, MIS
University of Amiens
33 rue Saint Leu, Amiens Cedex 1, 80039, FRANCE
$^1$e-mail: swan.dubois@etud.u-picardie.fr
$^2$e-mail: vassilis.giakoumakis@u-picardie.fr
$^3$e-mail: elmounir@u-picardie.fr


Abstract.Let $G$ be a graph, a split in $G$ is a bi-partition $(X,Y)$ of its vertex set $V(G)$ such that $\mid X\mid,\mid Y\mid\geq2$ and there are all possible edges between $X^{+}=X\cap N(Y)$ and $Y^{+}=Y\cap N(X)$, where $N(X)$ and $N(Y)$ are respectively neighborhood of $X$ and $Y$ in $G$. Let $X^{-}$ and $Y^{-}$ be respectively the sets $X \setminus X^{+}$ and $Y\setminus Y^{+}$. Whenever $X^{-}=\emptyset$ (resp. $Y^{-}=\emptyset$) the set $X$ (resp. $Y$) is a non-trivial module of $G$. Let $H$ be a graph without split containing $G$ as induced subgraph. We show that in the graph induced by $V(H)\setminus V(G)$ and for any split $(X,Y)$ of $G$ there exists a particular kind of graph the $(X,Y)$ -split-pseudopath. The structure of the split-pseudopath generalizes that of the $W$-pseudopath introduced by I. Zverovich in [#!8!#], where $W$ is a non trivial module of $G$.

Received: February 15, 2008

AMS Subject Classification: 05C75

Key Words and Phrases: module, split decomposition, modular decomposition, split-prime extension, prime extension, split-pseudopath

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 43
Issue: 3