Displaying 261 – 280 of 373

Showing per page

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning, Christian Löwenstein, Dieter Rautenbach (2010)

Discussiones Mathematicae Graph Theory

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Perfect connected-dominant graphs

Igor Edmundovich Zverovich (2003)

Discussiones Mathematicae Graph Theory

If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number γ c ( G ) of G. A graph G is called a perfect connected-dominant graph if γ ( H ) = γ c ( H ) for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.

Point-set domatic numbers of graphs

Bohdan Zelinka (1999)

Mathematica Bohemica

A subset D of the vertex set V ( G ) of a graph G is called point-set dominating, if for each subset S V ( G ) - D there exists a vertex v D such that the subgraph of G induced by S { v } is connected. The maximum number of classes of a partition of V ( G ) , all of whose classes are point-set dominating sets, is the point-set domatic number d p ( G ) of G . Its basic properties are studied in the paper.

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G , denoted by pc ( G ) , is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc ( G ) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2 -coloring for a connected bipartite graph G having δ ( G ) 2 and a dominating cycle...

Quasiperfect domination in triangular lattices

Italo J. Dejter (2009)

Discussiones Mathematicae Graph Theory

A vertex subset S of a graph G is a perfect (resp. quasiperfect) dominating set in G if each vertex v of G∖S is adjacent to only one vertex ( d v ∈ 1,2 vertices) of S. Perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol 3,6 and in its toroidal quotients are investigated, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form K ν , where ν ∈ 1,2,3 depends only on S.

Random procedures for dominating sets in bipartite graphs

Sarah Artmann, Jochen Harant (2010)

Discussiones Mathematicae Graph Theory

Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

Realizable triples for stratified domination in graphs

Ralucca Gera, Ping Zhang (2005)

Mathematica Bohemica

A graph is 2 -stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2 -stratified graph rooted at some blue vertex v . An F -coloring of a graph G is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v . The F -domination number γ F ( G ) is the minimum number of red vertices in an F -coloring of G . In this paper, we study F -domination where F is...

Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille

Mustapha Aouchiche, Odile Favaron, Pierre Hansen (2009)

RAIRO - Operations Research

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme b ̲ n g i b ¯ n où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne l ¯ , l'index λ1, l'indice de Randić R et le nombre de domination β, désigne l'une des opérations +, -, ×, /, b ̲ n et b ¯ n des fonctions de l'ordre n du graphe qui bornent l'expression g i et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

Relations between the domination parameters and the chromatic index of a graph

Włodzimierz Ulatowski (2009)

Discussiones Mathematicae Graph Theory

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality...

Remarks on Dynamic Monopolies with Given Average Thresholds

Carmen C. Centeno, Dieter Rautenbach (2015)

Discussiones Mathematicae Graph Theory

Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority...

Remarks on restrained domination and total restrained domination in graphs

Bohdan Zelinka (2005)

Czechoslovak Mathematical Journal

The restrained domination number γ r ( G ) and the total restrained domination number γ t r ( G ) of a graph G were introduced recently by various authors as certain variants of the domination number γ ( G ) of ( G ) . A well-known numerical invariant of a graph is the domatic number d ( G ) which is in a certain way related (and may be called dual) to γ ( G ) . The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.

Resolving domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2003)

Mathematica Bohemica

For an ordered set W = { w 1 , w 2 , , w k } of vertices and a vertex v in a connected graph G , the (metric) representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , , d ( v , w k ) ) , where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for G is its dimension dim G . A set S of vertices in G is a dominating set...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by γ r ( G ) , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γ r ( U ) n / 3 , and provide a characterization of graphs achieving this bound.

Currently displaying 261 – 280 of 373