On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Upper Bound on the Diameter of a Domination Dot-Critical Graph

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k??? 3 and diameter d and if G has no critical vertices, then d??? 2k?3.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

A decomposition approach for solving a broadcast domination network design problem

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f _i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f _k -value whose shortest distance to node j is no more than f _k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.     

Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Bounds related to domination in graphs with minimum degree two

A dominating set for a graph G = (V,E) is a subset of vertices V′ ⊆ V such that for all v E V − V′ there exists some u E V′ for which {v, u} E E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q edges, the domination number is bounded by (q + 1)/3. From this we derive exact lower bounds for the number of edges of a connected graph with minimum degree at least 2 and a given domination number. We also generalize the bound to k-restricted domination numbers; these measure how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be incluced in the dominating set. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 139–152, 1997     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

Path and cycle decompositions of complete equipartite graphs: Four parts

We show that a complete equipartite graph with four partite sets has an edge-disjoint decomposition into cycles of length k if and only if k≥3, the partite set size is even, k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k. We also show that a complete equipartite graph with four even partite sets has an edge-disjoint decomposition into paths with k edges if and only if k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k+1.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

On diameter critical graphs

A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v² edges, and (ii) average edge degree at most $\text{6}\text{5}$v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph.     

Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

The diameter of total domination vertex critical graphs

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γ_t-critical. If such a graph G has total domination number k, we call it k-γ_t-critical. We characterize the connected graphs with minimum degree one that are γ_t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γ_t-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).     

Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces

For a graph property P and a graph G, we define the domination subdivision number with respect to the property P to be the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to change the domination number with respect to the property P. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.     

Increasing the Weight of Minimum Spanning Trees

The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k)-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O(n³m² log(n²/m)) time algorithm is presented to solve it.     

A Note on Large Rainbow Matchings in Edge-coloured Graphs

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided ${n\geq \frac{17}{4}k^2}$ . In this paper, we show that n ≥ 4k ? 4 is sufficient for k ≥ 4.     

Solving NP-hard problems in ‘almost trees’: Vertex cover

We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time $\text{O}\text{(|V|+(}\text{a}\text{k}\text{)2}{}^{\mathrm{<mtext>k</mtext><mtext>3</mtext>}}\text{)}$, where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches.     

Network reinforcement

We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invulnerability of a network. Our algorithm has the same asymptotic complexity as |V| applications of the minimum cut algorithm of Goldberg & Tarjan. Received: April, 2004