8 results on '"Graph"'
Search Results
2. On the probabilistic minimum coloring and minimum -coloring
- Author
-
Murat, Cécile and Paschos, Vangelis Th.
- Subjects
- *
GRAPH theory , *ALGEBRA , *COMBINATORICS , *TOPOLOGY - Abstract
Abstract: We study a robustness model for the minimum coloring problem, where any vertex of the input-graph has some presence probability . We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of into independent sets , that minimizes the quantity , where, for any independent set , . We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min -Coloring) is NP-hard, for any . We finally study Probabilistic Min Coloring and Probabilistic Min -Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
3. Double Roman domination
- Author
-
Stephen T. Hedetniemi, Robert A. Beeler, and Teresa W. Haynes
- Subjects
Domination analysis ,Applied Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Upper and lower bounds ,Graph ,Algebra ,Combinatorics ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Connectivity ,Mathematics - Abstract
For a graph G = ( V , E ) , a double Roman dominating function is a function f : V ź { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v must have at least one neighbor with f ( w ) ź 2 . The weight of a double Roman dominating function f is the sum f ( V ) = ź v ź V f ( v ) , and the minimum weight of a double Roman dominating function on G is the double Roman domination number of G . We initiate the study of double Roman domination and show its relationship to both domination and Roman domination. Finally, we present an upper bound on the double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound.
- Published
- 2016
4. The signed Roman k-domatic number of a graph
- Author
-
Lutz Volkmann
- Subjects
Algebra ,Combinatorics ,Domatic number ,Vertex (graph theory) ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Graph ,Mathematics - Abstract
Let k ? 1 be an integer. A signed Roman k -dominating function on a graph G is a function f : V ( G ) ?s? { - 1 , 1 , 2 } such that ? u ? N v f ( u ) ? k for every v ? V ( G ) , where N v is the closed neighborhood of v , and every vertex u ? V ( G ) for which f ( u ) = - 1 is adjacent to at least one vertex w for which f ( w ) = 2 . A set { f 1 , f 2 , ? , f d } of distinct signed Roman k -dominating functions on G with the property that ? i = 1 d f i ( v ) ? k for each v ? V ( G ) , is called a signed Roman k -dominating family (of functions) on G . The maximum number of functions in a signed Roman k -dominating family on G is the signed Roman k -domatic number of G , denoted by d s R k ( G ) . In this paper we initiate the study of signed Roman k -domatic numbers in graphs, and we present sharp bounds for d s R k ( G ) . In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed Roman k -domatic number of some graphs.
- Published
- 2015
5. On difference of Zagreb indices
- Author
-
Boris Furtula, Ivan Gutman, and Süleyman Ediz
- Subjects
Vertex (graph theory) ,Combinatorics ,Algebra ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Graph ,Mathematics - Abstract
The classical first and second Zagreb indices of a graph G are defined as M 1 = ∑ v d v 2 and M 2 = ∑ u v d u d v , where d v is the degree of the vertex v of G . So far, the difference of M 1 and M 2 has not been studied. We show that this difference is closely related to the vertex-degree-based invariant R M 2 = ∑ u v ( d u − 1 ) ( d v − 1 ) , and determine a few basic properties of R M 2 .
- Published
- 2014
6. List backbone colouring of graphs
- Author
-
Stephen Finbow, Yuehua Bu, Xuding Zhu, and Daphne Der-Fen Liu
- Subjects
Algebra ,Combinatorics ,Vertex (graph theory) ,Choice number ,Subgroup ,Applied Mathematics ,Complete graph ,Discrete Mathematics and Combinatorics ,Graph ,Mathematics ,Channel assignment problem - Abstract
Suppose that G is a graph and that H is a subgraph of G. Let L be a mapping that assigns to each vertex v of G a set L(v) of positive integers. We say that (G,H) is backboneL-colourable if there is a proper vertex colouring c of G such that c(v)@?L(v) for all [email protected]?V, and |c(u)-c(v)|>=2 for every edge uv in H. We say that (G,H) is backbone k-choosable if (G,H) is backbone L-colourable for any list assignment L with |L(v)|=k for all [email protected]?V(G). The backbone choice number of (G,H), denoted by ch"B"B(G,H), is the minimum k such that (G,H) is backbone k-choosable. The concept of a backbone choice number is a generalization of both the choice number and the L(2,1)-choice number. Precisely, if E(H)[email protected]?, then ch"B"B(G,H)=ch(G), where ch(G) is the choice number of G; if G=H^2, then ch"B"B(G,H) is the same as the L(2,1)-choice number of H. In this article, we first show that, if |L(v)|=d"G(v)+2d"H(v), then (G,H) is L-colourable, unless E(H)[email protected]? and each block of G is a complete graph or an odd cycle. This generalizes a result of Erdos, Rubin, and Taylor on degree-choosable graphs. Second, we prove that ch"B"B(G,H)=
- Published
- 2014
7. A tight upper bound for 2-rainbow domination in generalized Petersen graphs
- Author
-
Yue-Li Wang and Kuo-Hua Wu
- Subjects
Vertex (graph theory) ,Combinatorics ,Algebra ,Domination analysis ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Rainbow ,Generalized Petersen graph ,Upper and lower bounds ,Graph ,Mathematics - Abstract
Let f be a function that assigns to each vertex a subset of colors chosen from a set C={1,2,...,k} of k colors. If @?"u"@?"N"("v")f(u)=C for each vertex [email protected]?V with f(v)[email protected]?, then f is called a k-rainbow dominating function (kRDF) of G where N(v)={[email protected]?V|[email protected]?E}. The weight of f, denoted by w(f), is defined as w(f)[email protected]?"v"@?"V|f(v)|. Given a graph G, the minimum weight among all weights of kRDFs, denoted by @c"r"k(G), is called the k-rainbow domination number of G. [email protected]?ar and [email protected]?umenjak (2007) [5] gave an upper bound and a lower bound for @c"r"2(GP(n,k)). They showed that @[email protected]?=
- Published
- 2013
8. On thet-pebbling number and the2t-pebbling property of graphs
- Author
-
Ze-Tu Gao and Jian-Hua Yin
- Subjects
Combinatorics ,Algebra ,symbols.namesake ,Conjecture ,Applied Mathematics ,Complete graph ,symbols ,Discrete Mathematics and Combinatorics ,Cartesian product ,Graph ,Connectivity ,Mathematics ,Vertex (geometry) - Abstract
Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The t-pebbling [email protected]"t(G) is the smallest positive integer such that, for every distribution of @p"t(G) pebbles and every vertex v, t pebbles can be moved to v. For t=1, Graham conjectured that @p"1([email protected]?H)@[email protected]"1(G)@p"1(H) for any connected graphs G and H, where [email protected]?H denotes the Cartesian product of G and H. Herscovici further conjectured that @p"s"t([email protected]?H)@[email protected]"s(G)@p"t(H). In this paper, we show that @p"s"t([email protected]?G)@[email protected]"s(T)@p"t(G), @p"s"t(K"[email protected]?G)@[email protected]"s(K"n)@p"t(G) and @p"s"t(C"2"[email protected]?G)@[email protected]"s(C"2"n)@p"t(G) when G has the 2t-pebbling property, T is a tree, K"n is the complete graph on n vertices, and C"2"n is the cycle on 2n vertices, which confirms a conjecture due to Lourdusamy. Moreover, we also show that any graph G with diameter 2 and @p"t(G)[email protected](G)+4(t-1) has the 2t-pebbling property, which extends a result of Pachter et al.
- Published
- 2013
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.