1. Equality of graphs up to complementation
- Author
-
Hamza Si Kaddour, Gérard Lopez, Jamel Dammak, Département de Mathematiques [Sfax], Faculté des Sciences de Sfax, Université de Sfax - University of Sfax-Université de Sfax - University of Sfax, Institut de mathématiques de Luminy (IML), Université de la Méditerranée - Aix-Marseille 2-Centre National de la Recherche Scientifique (CNRS), Combinatoire, théorie des nombres (CTN), Institut Camille Jordan (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
05C60 ,General Mathematics ,Modulo ,010102 general mathematics ,01 natural sciences ,Prime (order theory) ,010101 applied mathematics ,Combinatorics ,Integer ,05C50 ,[MATH]Mathematics [math] ,0101 mathematics ,Complement (set theory) ,Mathematics - Abstract
We prove the following: Let G and $$G'$$ G ′ be two graphs on the same set V of v vertices, and let k be an integer, $$4\le k\le v-4$$ 4 ≤ k ≤ v - 4 . If for all k-element subsets K of V, the induced subgraphs $$G_{\restriction K}$$ G ↾ K and $$G'_{\restriction K}$$ G ↾ K ′ have the same numbers of 3-homogeneous subsets, the same numbers of $$P_4$$ P 4 ’s, and the same numbers of claws or co-claws, then $$G'$$ G ′ is equal to G or to the complement $$\overline{G}$$ G ¯ of G. We give also a similar result whenever the same numbers are modulo a prime.
- Published
- 2020
- Full Text
- View/download PDF