Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Colorations généralisées, graphes biorientés et deux ou trois choses sur François

Abdelkader Khelladi — 1999

Annales de l'institut Fourier

La généralisation des nombres chromatiques χ n ( G ) de Stahl a été un premier thème de travail avec François et a abouti à l’introduction de la notion de colorations généralisées et leurs nombres chromatiques associés, notées χ n p , q ( G ) . Cette nouvelle notion a permis d’une part, d’infirmer avec Payan une conjecture posée par Brigham et Dutton, et d’autre part, d’étendre de manière naturelle la formule de récurrence de Stahl aux nombres chromatiques χ n 0 , q ( G ) . Cette relation s’exprime comme χ n 0 , q ( G ) χ n - 1 0 , q ( G ) + 2 . La conjecture de Bouchet...

Exact double domination in graphs

Mustapha ChellaliAbdelkader KhelladiFrédéric Maffray — 2005

Discussiones Mathematicae Graph Theory

In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive...

Transitive closure and transitive reduction in bidirected graphs

Ouahiba BessoufAbdelkader KhelladiThomas Zaslavsky — 2019

Czechoslovak Mathematical Journal

In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.

Page 1

Download Results (CSV)