Search

In a graph G = (V , E) , a module is a vertex subset M of V such that every vertex outside M is adjacent to all or none of M. For example, ∅ , { x } (x ∈ V) and V are modules of G , called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex x of a prime graph G is critical if G − x is decomposable. Moreover, a prime graph with k noncritical vertices is called (− k) -critical graph. A prime graph G is k -minimal if there is some k -vertex set X of vertices such that there is no proper induced subgraph of G containing X is prime. From this perspective, Boudabbous proposes to find the (− k) -critical graphs and k -minimal graphs for some integer k even in a particular case of graphs. This research paper attempts to answer Boudabbous's question. First, we describe the (− k) -critical tree. As a corollary, we determine the number of nonisomorphic (− k) -critical tree with n vertices where k ∈ { 1 , 2 , ⌊ n 2 ⌋ }. Second, we provide a complete characterization of the k -minimal tree. As a corollary, we determine the number of nonisomorphic k -minimal tree with n vertices where k ≤ 3. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a new coloring problem of graphs called the double total dominator coloring. A double total dominator coloring of a graph G with minimum degree at least 2 is a proper vertex coloring of G such that each vertex has to dominate at least two color classes. The minimum number of colors among all double total dominator coloring of G is called the double total dominator chromatic number, denoted by χ d d t (G). Therefore, we establish the close relationship between the double total dominator chromatic number χ d d t (G) and the double total domination number γ × 2 , t (G). We prove the NP-completeness of the problem. We also examine the effects on χ d d t (G) when G is modified by some operations. Finally, we discuss the χ d d t (G) number of square of trees by giving some bounds. [ABSTRACT FROM AUTHOR]

In a graph G = (V, E), a module is a vertex subset M such that every vertex outside M is adjacent to all or none of M. For example, ϕ, {x} (x∊ V) and V are modules of G, called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex x of a prime graph G is critical if G - x is decomposable. We generalize this definition. A prime graph G = (V, E) is Xcritical, where X is a subset of V, if for each x ∊ X, x is a critical vertex. Moreover, G is (-k)-critical, where 0 = k = |V|, if G is (V\X)-critical for some subset X of V such that |X| = k. In 1993, J.H. Schmerl and W.T. Trotter characterized the V-critical graphs, called critical graphs with vertex set V. Recently, H. Belkhechine, I. Boudabbous and M.B. Elayech characterized the (-1)-critical graphs. In this paper, we characterize the (-k)-critical graphs within the family of triangle-free graphs where k = 2. [ABSTRACT FROM AUTHOR]