1. Detection number of bipartite graphs and cubic graphs
- Author
-
Nagarajan Paramaguru, Rathinaswamy Sampathkumar, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Mathematics Wing, Directorate of Distance Education [India], Annamalai University, Mathematics Section [India], ANR-09-BLAN-0373,GraTel(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), and INRIA
- Subjects
Discrete mathematics ,General Computer Science ,Foster graph ,cubic graph ,Neighbourhood (graph theory) ,bipartite grap ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Gray graph ,NP-completeness ,Theoretical Computer Science ,detectable coloring ,Combinatorics ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,Edge-transitive graph ,Graph power ,Bipartite graph ,Discrete Mathematics and Combinatorics ,Bound graph ,Graph toughness ,Mathematics - Abstract
For a connected graph G of order |V(G)| ≥ 3 and a k-labelling c : E(G) → {1,2, . . . ,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1, ℓ2, . . . , ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-labelling is the detection number of G. In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is 2. We also show that the detection number of every bipartite graph of minimum degree at least 3 is at most 2. Finally, we give some sufficient condition for a cubic graph to have detection number 3.; Pour un graphe connexe G d'ordre |V(G)| ≥ 3 et un étiquetage c : E(G) → {1,2, . . . ,k} des arêtes de G, le code d'un sommet v de G est le k-uplet (ℓ1, ℓ2, . . . , ℓk), où ℓi est le nombre d'arêtes incidentes à v qui sont étiquetées i. Le k-étiquetage c est détectable si, quels que soient deux sommets adjacents de G, leurs codes sont distincts. Le plus petit entier strictement positif k pour lequel G a un k-étiquetage détectable est l'indice de détection det(G) de G. Dans ce rapport, nous montrons qu'il est NP-complet de décider si l'indice de détection d'une graphe cubique vaut 2. Nous montrons également que l'indice de détection de tout graphe biparti de degré minimum au moins 3 est au plus 2. Enfin, nous donnons des conditions suffisantes pour qu'un graphe cubique soit d'indice de détection 3.
- Published
- 2014
- Full Text
- View/download PDF