Equality of graphs up to complementation
- PDF / 404,128 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 13 Downloads / 196 Views
Arabian Journal of Mathematics
Jamel Dammak · Gérard Lopez · Hamza Si Kaddour
Equality of graphs up to complementation
Received: 15 June 2019 / Accepted: 21 September 2020 © The Author(s) 2020
Abstract We prove the following: Let G and G be two graphs on the same set V of v vertices, and let k be an integer, 4 ≤ k ≤ v − 4. If for all k-element subsets K of V , the induced subgraphs G K and G K have the same numbers of 3-homogeneous subsets, the same numbers of P4 ’s, and the same numbers of claws or co-claws, then G is equal to G or to the complement G of G. We give also a similar result whenever the same numbers are modulo a prime. Mathematics Subject Classfication
05C50 · 05C60
1 Introduction and main results Our notations and terminology follow [2]. A symmetric graph (or more simply graph) is an ordered pair G := (V, E ), where E is a subset of [V ]2 , the set of pairs {x, y} of distinct elements of V . Elements of V are the vertices of G and elements of E its edges. If K is a subset of V , the restriction of G to K , also called the induced graph on K is the graph G K := (K , [K ]2 ∩ E ). The complement of G is the graph G := (V, [V ]2 \ E ). We denote by V (G) the vertex set of a graph G, by E(G) its edge set and by e(G) := |E(G)| the number of edges. Let G := (V, E) be a graph. A 3-element subset T of V such that all pairs belong to E(G) is a triangle of G. A 3-element subset of V which is a triangle of G or of G is a 3-homogeneous subset of G. We denote by K 3 the complete graph on 3 vertices and by K 1,3 the graph made of a vertex linked to a K 3 . The graph K 1,3 is called a claw, the graph K 1,3 a co-claw. For these graphs, see Fig. 1. In memory of Gérard Lopez with all our affection and admiration. Gérard Lopez died on April 8, 2019; this work was at the end of writing. Deceased: Gérard Lopez J. Dammak Department of Mathematics, Faculty of Sciences of Sfax, B.P. 1171, 3000 Sfax, Tunisia E-mail: [email protected] G. Lopez Institut de Mathématiques de Luminy, CNRS-UPR 9016,163 avenue de Luminy, case 907, 13288 Marseille cedex 9, France E-mail: [email protected] H. Si Kaddour (B) Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 blvd. du 11 novembre 1918, 69622 Villeurbanne cedex, France E-mail: [email protected]
123
Arab. J. Math.
K3
K 1,3
K 1,3
P4
Fig. 1 K 3 , K 1,3 , K 1,3 , P4
Given two graphs G := (V, E) and G := (V , E ). A bijection f from V onto V is an isomorphism from G onto G provided that for any x, y ∈ V , {x, y} ∈ E if and only if { f (x), f (y)} ∈ E . The graphs G and G are isomorphic, which is denoted by G G , if there exists an isomorphism from one onto the other, otherwise G G . Let G, G be two graphs on the same vertex set V . We say that G and G are equal up to complementation if G = G or G = G. If G has the same number of edges as G or G, we say that G and G have the same number of edges up to complementation. We say that G and G are isomorphic up to complementation if G
Data Loading...
