Research PaperNo Access

Unstable graphs and packing into fifth power

Mohammad Alzohairi

Department of Mathematics, King Saud University, P. O. Box 2455, Riyadh 11451, Saudi Arabia

E-mail Address: zohairi@ksu.edu.sa

Corresponding author.

Search for more papers by this author

Tarak Louleb

Department of Mathematics, Faculty of Science of Sfax, Soukra Road km 4, P. O. Box 802, 3018 Sfax, Tunisia

E-mail Address: tarekloleb@hotmail.com

Search for more papers by this author

, and

Mohamed Y. Sayar

Department of Mathematics, Faculty of Science of Sfax, Soukra Road km 4, P. O. Box 802, 3018 Sfax, Tunisia

E-mail Address: sayar_mohamed@yahoo.fr

Search for more papers by this author

https://doi.org/10.1142/S1793830923500593Cited by:0 (Source: Crossref)

Abstract

In a graph $G : = (V (G), E (G))$ , a subset $M$ of the vertex set $V (G)$ is a module (or interval, clan) of $G$ if every vertex outside $M$ is adjacent to all or none of $M$ . The empty set, the singleton sets, and the full set of vertices are trivial modules. The graph $G$ is indecomposable (or prime) if all its modules are trivial. If $G$ is indecomposable, we say that an edge $e$ of $G$ is a removable edge if $G - e$ is indecomposable (here $G - e : = (V (G), E (G) - {e})$ ). The graph $G$ is said to be unstable if it has no removable edges. For a positive integer $k$ , the $k$ th power $G^{k}$ of a graph $G$ is the graph obtained from $G$ by adding an edge between all pairs of vertices of $G$ with distance at most $k$ . A graph $G$ of order $n$ (i.e., $| V (G) | = n$ ) is said to be $p$ -placeable into $G^{k}$ , if $G^{k}$ contains $p$ edge-disjoint copies of $G$ . In this paper, we answer a question, suggested by Boudabbous in a personal communication, concerning unstable graphs and packing into their fifth power as follows: First, we give a characterization of the unstable graphs which is deduced from the results given by Ehrenfeucht, Harju and Rozenberg (the theory of $2$ -structures: a framework for decomposition and transformation of graphs). Second, we prove that every unstable graph $G$ is $2$ -placeable into $G^{5}$ .

Communicated by Xiao-Dong Zhang

Keywords:

AMSC: 05C99

References

1. D. Burns and S. Schuster , Embedding (p, p-1) graphs in their complements, Israel J. Math. 30(4) (1978) 313–320. Crossref, Google Scholar
2. A. Ehrenfeucht, T. Harju and G. Rozenberg , The Theory of 2-Structures: A Framework for Decomposition and Transformation of Graphs (World Scientific Publishing Company, 1999). Link, Google Scholar
3. R. J. Faudree, C. C. Rousseau, R. H. Schelp and S. Schuster , Embedding graphs in their complements, Czechoslov. Math. J. 31(1) (1981) 53–62. Crossref, Google Scholar
4. A. Görlich, M. Pilśniak, M. Woźniak and I. A. Zioło , A note on embedding graphs without short cycles, Discrete Math. 286(1) (2004) 75–77. Crossref, Google Scholar
5. S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater , A note on packing two trees into kn, Ars Combin. 11 (1981) 149–153. Google Scholar
6. A. Kaneko and K. Suzuki , Packing two copies of a tree into its third power, Discrete Math. 306(21) (2006) 2779–2785. Crossref, Google Scholar
7. H. Kheddouci, J.-F. Saclé and M. Woźniak , Packing two copies of a tree into its fourth power, Discrete Math. 213(1–3) (2000) 169–178. Crossref, Google Scholar
8. D. P. Sumner , Graphs indecomposable with respect to the x-join, Discrete Math. 6(3) (1973) 281–298. Crossref, Google Scholar
9. M. Woźniak , Packing of graphs and permutations — a survey, Discrete Math. 276(1) (2004) 379–391. Crossref, Google Scholar
10. H. P. Yap , Packing of graphs — a survey, Discrete Math. 72(1) (1988) 395–404. Crossref, Google Scholar