Search

Let G = (V , E) be a nontrivial connected simple graph and d (a , b) be the distance between the vertices a and b in G. The metric dimension of a graph G , denoted by dim(G), refers to the smallest set of vertices required to uniquely identify every vertex in the graph G. A family of simple connected graphs say F s , where s ∈ ℕ has a constant metric dimension, if dim ( F s ) is finite and does not depend on the choice of s in F s . In this paper, we consider two infinite families of planar graphs, say Q s , where s ≥ 8 and Z s , where s ≥ 6 , and investigate their metric basis as well as the metric dimension. Additionally, we prove that the metric basis for these two graphs are independent. [ABSTRACT FROM AUTHOR]

Harary and Melter introduced the concept of resolving sets in graphs. Slater stated the term locating set and the minimum resolving set as reference sets. Chartrand mentioned the locating set as a resolving set and the minimum cardinality of a resolving set as metric dimension or simply dimension in later stage. Several types of resolving sets like connected resolving sets, independent resolving sets, acyclic resolving sets, etc. have been discussed in the past. In this work, weakly connected resolving set is introduced and we studied its bounds. [ABSTRACT FROM AUTHOR]

A set S ⊆ V of vertices in a graph G = (V , E) is called a dominating set if every vertex in V − S is adjacent to a vertex in S. Hamid defined a dominating set which intersects every maximum independent set in G to be an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by γ it (G). In this paper we prove that for trees T , γ it (T) is bounded above by ⌈ n 2 ⌉ and characterize the extremal trees. Further, we characterize the class of all trees whose independent transversal domination number does not alter owing to the deletion of an edge. [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Let H = (V , E) be a connected graph of size n. If W is an ordered subset of distinct vertices in H then the subset W is said to be a resolving set for H , if all of the vertices in the graph can be uniquely defined by the vector of distances to the vertices in W. A resolving set W with minimum possible vertices is said to be a metric basis for H. The cardinality of the metric basis is called the metric dimension of the graph H. In this paper, we demonstrate that the metric dimension for some families of related planar graphs is three. [ABSTRACT FROM AUTHOR]

In this paper, we give a class of graphs that do not admit disjoint maximum and maximal independent (MMI) sets. The concept of inverse independence was introduced by Bhat and Bhat in [Inverse independence number of a graph, Int. J. Comput. Appl. 42(5) (2012) 9–13]. Let A be a α -set in G. An independent set D ⊂ V (G) − A is called an inverse independent set with respect to A. The inverse independence number α − 1 (G) is the size of the largest inverse independent set in G. Bhat and Bhat gave few bounds on the independence number of a graph, we continue the study by giving some new bounds and exact value for particular classes of graphs: spider tree, the rooted product and Cartesian product of two particular graphs. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-cliquesubgraph of a graph is an induced subgraph whose maximum clique has at most k vertices. We describe a polynomial time algorithm to find a maximum weight max- k -clique subgraph in a cactus subtree graph when k is fixed. In perfect graphs this problem is equivalent to the maximum weight k -colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max- k -clique subgraph solution is better than a maximum k -colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets. [ABSTRACT FROM AUTHOR]

For a given graph H , the independence number α (H) of H is the size of the maximum independent set of V (H). Finding the maximum independent set in a graph is NP-hard. Another version of the independence number is defined as the size of the maximum-induced forest of H , and called the forest number of H , and denoted by f (H). Finding f (H) is also an NP-hard problem. Suppose that H = (V (H) , E (H)) is a graph, and is a family of graphs, a graph H has a -free k -coloring if there exists a decomposition of V (H) into sets V i , i = 1 , 2 , ... , k , so that G ⊈ H [ V i ] for each i , and each G ∈ . S ⊆ V (H) is G -free, if the subgraph of H induced by S is G -free, i.e., it contains no copy of G. Finding a maximum subset S of H , such that H [ S ] is a G -free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also, we give some bounds about the size of the maximum G -free subset of graphs as another purpose of this paper. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A subset F of E is called a line-set dominating set (LSD-set) if for each subset L ⊆ E ∖ F , there exists an edge e ∈ F such that the edge-induced subgraph 〈 L ∪ { e } 〉 is connected. The minimum cardinality of an LSD-set of G is called the line-set domination number of G and is denoted by γ lsd (G). In this paper, we obtain a sharp upper bound on the diameter of G which has an independent LSD-set and on the diameter of graph G satisfying γ l (G) = γ lsd (G) where γ l (G) is the line domination number of G. [ABSTRACT FROM AUTHOR]

A dominating set D ⊆ V (G) is called a connected co-independent dominating set of G , where G is a finite simple undirected graph, if D is a connected dominating set of G and V (G) ∖ D is an independent set. The minimum cardinality of such a set, denoted by γ c , coi (G) , is called the connected co-independent domination number of G. In this paper, we study this concept and the corresponding parameter in graphs resulting from the join, corona and lexicographic product of two graphs. Specifically, we characterize the connected co-independent dominating sets in these types of graphs and determine the exact values of their connected co-independent domination numbers. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a non-empty, finite graph. If the vertices of G can be bijectively labeled by a set S of positive distinct real numbers with two vertices being adjacent if and only if the positive difference of the corresponding labels is in S, then G is called a proper monograph. The set S is called the signature of G and denoted as G(S). Not all proper monographs have the property that a set of idle vertices can be bijectively mapped to the maximum independent sets. As a result, in this paper, we present the proper monograph labelings of several classes of graphs that satisfy the property mentioned above. We present the proper monograph labelings of graphs such as cycles, C n ⊙ K 1 , cycles with paths attached to one or more vertices, and Cycles with an irreducible tree attached to one or more vertices. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of B 1 -VPG graphs when the input is specified by a B 1 -VPG representation. We obtain a 6 (log n) 2 -approximation algorithm running in O (n (log n) 3) time. This is an improvement over the previously best n -approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed > 0) designed for some subclasses of string graphs, on B 1 -VPG graphs. [ABSTRACT FROM AUTHOR]

We introduce and study an inductively defined analogue f IND () of any increasing graph invariant f (). An invariant f () is increasing if f (H) ≤ f (G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing f () , this gets us several new invariants and many of which are also increasing. It is also shown that f IND () is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing f IND () (and a corresponding optimal vertex ordering) and identify some pairs (, f ()) for which f IND () can be computed efficiently for members of . In particular, it includes graphs of bounded f IND () values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing f () to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r -neighborhoods for arbitrary but fixed r ≥ 1. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms  8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced -subgraphs and optimal -colorings (for hereditary 's) within multiplicative factors of (essentially) k and k / (m − 1) , respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced -subgraph of the input and m is the minimum size of a forbidden induced subgraph of . Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal -subgraphs and -colorings for arbitrary hereditary classes . As a corollary, it is also shown that any maximal -subgraph approximates an optimal solution within a factor of k + 1 for unweighted graphs, where k is maximum size of any induced -subgraph in any local neighborhood N G (u). [ABSTRACT FROM AUTHOR]

We introduce and study an inductively defined analogue f IND () of any increasing graph invariant f (). An invariant f () is increasing if f (H) ≤ f (G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing f () , this gets us several new invariants and many of which are also increasing. It is also shown that f IND () is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing f IND () (and a corresponding optimal vertex ordering) and identify some pairs (, f ()) for which f IND () can be computed efficiently for members of . In particular, it includes graphs of bounded f IND () values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing f () to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r -neighborhoods for arbitrary but fixed r ≥ 1. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms  8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced -subgraphs and optimal -colorings (for hereditary 's) within multiplicative factors of (essentially) k and k / (m − 1) , respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced -subgraph of the input and m is the minimum size of a forbidden induced subgraph of . Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal -subgraphs and -colorings for arbitrary hereditary classes . As a corollary, it is also shown that any maximal -subgraph approximates an optimal solution within a factor of k + 1 for unweighted graphs, where k is maximum size of any induced -subgraph in any local neighborhood N G (u). [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a connected graph. A function f : V → { 0 , 1 , 2 } is called a Roman dominating function if every vertex v with f (v) = 0 is adjacent to a vertex u with f (u) = 2. If further the set V 0 = { v : f (v) = 0 } is an independent set, then f is called an outer independent Roman dominating function (OIRDF). Let w (f) = ∑ v ∈ V f (v) and γ oiR (G) = min { w (f) : f  is an OIRDF of  G }. Then γ o i R (G) is called the outer independent Roman domination number of G. In this paper, we prove that the decision problem for γ o i R (G) is NP-complete for chordal graphs. We also show that γ o i R (G) is linear time solvable for threshold graphs and bounded tree width graphs. Moreover, we show that the domination and outer independent Roman domination problems are not equivalent in computational complexity aspects. [ABSTRACT FROM AUTHOR]

The problem of characterizing the classes of plane graphs with the bounded metric dimension, edge metric dimension, and fault-tolerant metric dimension is of great interest nowadays. In this paper, we study the metric dimension, the fault-tolerant metric dimension, and the edge metric dimension of a two-fold heptagonal-nonagonal circular ladder (denoted by ℍ n 7 , 9 ). We show that the metric dimension and the edge metric dimension of ℍ n 7 , 9 are the same. We also study its fault-tolerant metric dimension and prove that the metric basis and the edge metric basis sets are independent. [ABSTRACT FROM AUTHOR]

Let A (n , d) be the size of the maximum binary code of length n and minimum Hamming distance d. A (n , d , w) is defined similarly for binary code with constant weight w. Obviously, finding the value of A (n , d) is equivalent to finding the maximum independent set of the d − 1 th-power of n -dimensional hypercube. Based on this, this paper obtains that A (3 m , 2 m) = 4 , A (m (m + 1) 2 , 2 m − 2 , m) = m + 1 , A (2 m + 1 − 2 , 2 m − 1) = 2 m + 1 , and explores the structure of the maximum code of length 2 m + 2 and minimum Hamming distance 2 m + 1 , where m is an integer. [ABSTRACT FROM AUTHOR]

Let G A be a family of graphs and let J be a set of connected graphs, each with at most r vertices, r fixed. A J -packing of a graph GA is a vertex induced subgraph of GA with every connected component isomorphic to a member of J. A maximum weight k -covering of a graph GA by J -packings, is a maximum weight subgraph of GA exactly covered by k vertex disjoint J -packings. For a graph G A ∈ G A let J (GA) be a graph, every vertex v of which corresponds to a vertex subgraph a (v) of GA isomorphic to a member of J , two vertices u , v of J (GA) being adjacent if and only if a (u) and a (v) have common vertices or interconnecting edges. The closed neighborhoods containment graph C N C G (G A) of a graph G A (V , D) ∈ G A , is the graph with vertex set V and edges directed from vertices u to v if and only if they are adjacent in GA and the closed neighborhood of u is contained in the closed neighborhood of v. A graph G (V , E) is a G A − H reduced graph if it can be obtained from a graph G A (V , D) ∈ G A by deleting the edges of a transitive subgraph H of CNCG(GA). We describe 1.582-approximation algorithms for maximum weight k -coverings by J -packings of G A and G A − H reduced graphs when G A is vertex hereditary, has an algorithm for maximum weight independent set and J (G A) ⊆ G A. These algorithms can be applied to families of interval filament, subtree filament, weakly chordal, AT-free and circle graphs, to find 1.582 approximate maximum weight k -coverings by vertex disjoint induced matchings, dissociation sets, forests whose subtrees have at most r vertices, etc. [ABSTRACT FROM AUTHOR]

Let Σ = (G , E , σ) be a signed graph. A dominating set S ⊆ V is said to be an independent dominating set of Σ if 〈 S 〉 is a fully negative. In this paper, we initiate a study of this parameter. We also establish the bounds and characterization on the independent domination number of a signed graph. [ABSTRACT FROM AUTHOR]

A set S ⊆ V of vertices in a graph G = (V , E) is called a dominating set if every vertex in V − S is adjacent to a vertex in S. An independent transversal dominating set in a graph G is a dominating set which intersects every maximum independent set of G. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G denoted by γ it (G). In this paper, we characterize those trees whose independent transversal domination number does not alter owing to the deletion of a vertex. [ABSTRACT FROM AUTHOR]

A k vertex coloring of a graph G = (V , E) partitions the vertex set into k color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in G dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A subset S ⊆ V of vertices is a dominating set if every vertex in V − S is adjacent to at least one vertex of S. The domination number is the minimum cardinality of a dominating set. Let u , v ∈ V. Then, u strongly dominates v and v weakly dominates u if (i) u v ∈ E and (ii) deg u ≥ deg v. A subset D of V is a strong (weak) dominating set of G if every vertex in V − D is strongly (weakly) dominated by at least one vertex in D. The strong (weak) domination number of G is the minimum cardinality of a strong (weak) dominating set. A set D ⊆ V is an independent (or stable) set if no two vertices of D are adjacent. The independent domination number of G (independent strong domination number, independent weak domination number, respectively) is the minimum size of an independent dominating set (independent strong dominating set, independent weak dominating set, respectively) of G. In this paper, mathematical models are developed for the problems of independent domination and independent strong (weak) domination of a graph. Then test problems are solved by the GAMS software, the optima and execution times are implemented. To the best of our knowledge, this is the first mathematical programming formulations for the problems, and computational results show that the proposed models are capable of finding optimal solutions within a reasonable amount of time. [ABSTRACT FROM AUTHOR]

A random geometric graph, G (n , r) , is formed by choosing n points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most r. For a given constant k , we show that n − k 2 k − 2 is a distance threshold function for G (n , r) to have a connected subgraph on k points. Based on this, we show that n − 2 / 3 is a distance threshold for G (n , r) to be plane, and n − 5 / 8 is a distance threshold to be planar. We also investigate distance thresholds for G (n , r) to have a non-crossing edge, a clique of a given size, and an independent set of a given size. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A vertex u ∈ V strongly (weakly) b-dominates block b ∈ B (G) if d vb (u) ≥ d vb (w) ( d vb (u) ≤ d vb (w)) for every vertex w in the block b. A set S ⊆ V is said to be strong (weak) vb-dominating set (SVBD-set) (WVBD-set) if every block in G is strongly (weakly) b-dominated by some vertex in S. The strong (weak) vb-domination number γ svb = γ svb (G) ( γ wvb = γ wvb (G)) is the order of a minimum SVBD (WVBD) set of G. A set S ⊆ V is said to be strong (weak) vertex block independent set (SVBI-set (WVBI-set)) if S is a vertex block independent set and for every vertex u ∈ S and every block b incident on u , there exists a vertex w ∈ V − S in the block b such that d vb (u) ≥ d vb (w) ( d vb (u) ≤ d vb (w)). The strong (weak) vb-independence number β svb = β svb (G) ( β wvb = β wvb (G)) is the cardinality of a maximum strong (weak) vertex block independent set (SVBI-set) (WVBI-set) of G. In this paper, we investigate some relationships between these four parameters. Several upper and lower bounds are established. In addition, we characterize the graphs attaining some of the bounds. [ABSTRACT FROM AUTHOR]

Counting dominating sets in a graph is a #P-complete problem even in planar graphs. This paper studies this problem for generalized series-parallel graphs, which are a subclass of planar graphs. This work develops some linear-time algorithms for counting dominating sets and their two variants, independent dominating sets and connected dominating sets in generalized series-parallel graphs. [ABSTRACT FROM AUTHOR]

A k -tree is a tree with maximum degree at most k. For a graph G and u , v ∈ V (G) with u v ∉ E (G) , let α (u , v ; G) be the cardinality of a maximum independent set containing u and v. For a graph G and u , v ∈ V (G) , the local connectivity κ (u , v ; G) is defined to be the maximum number of internally disjoint paths connecting u and v in G. In this paper, we prove the following theorem and show the condition is sharp. Let k , s and t be integers with k ≥ 3 , 0 ≤ s ≤ k and 2 ≤ t ≤ k. For any two nonadjacent vertices u and v of G , we have κ (u , v ; G) ≥ s + 1 and α (u , v ; G) ≤ (κ (u , v ; G) − s) (k − 1) + s (t − 1) + 1. Then for any s distinct vertices of G , G has a spanning k -tree such that each of s specified vertices has degree at most t. This theorem implies H. Matsuda and H. Matsumura's result in [on a k -tree containing specified cleares in a graph, Graphs Combin.22 (2006) 371–381] and V. Neumann-Lara and E. Rivera-Campo's result in [Spanning trees with bounded degrees, Combinatorica11 (1991) 55–61]. [ABSTRACT FROM AUTHOR]

Given a graph and an independent set of , the 0-1 inverse maximum independent set problem (IMIS) is to delete as few vertices as possible such that becomes a maximum independent set of . It is known that IMIS is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS on forests and unicyclic graphs. [ABSTRACT FROM AUTHOR]

A set S ⊆ V(G) is an independent set if no two vertices of S are adjacent. An independent set S such that 〈V - S〉 is connected is called an outer-connected independent set (oci-set). An oci-set is maximal if it is not a proper subset of any oci-set. The minimum and maximum cardinality of a maximal oci-set are called respectively the outer-connected independence number and the upper outer-connected independence number. This paper initiates a study of these parameters. [ABSTRACT FROM AUTHOR]

The independence number of a graph is defined as the maximum size of a set of pairwise non-adjacent vertices and the spectral radius is defined as the maximum eigenvalue of the adjacency matrix of the graph. Xu et al. in [The minimum spectral radius of graphs with a given independence number, Linear Algebra and its Applications 431 (2009) 937-945] determined the connected graphs of order n with independence number which minimize the spectral radius. In this paper, we show that the graph obtained from a path of order α by blowing up each vertex to a clique of order k minimizes the spectral radius among all connected graphs of order kα with independence number α for α = 3, 4 and conjecture that this is true for all α ∈ ℕ. [ABSTRACT FROM AUTHOR]

Two vertices u, w ∈ V, vv-dominate each other if they are incident on the same block. A set S ⊆ V is a vv-dominating set (VVD-set) if every vertex in V - S is vv-dominated by a vertex in S. The vv-domination number γvv = γvv(G) is the cardinality of a minimum VVD-set of G. Two blocks b1, b2 ∈ B(G) the set of all blocks of G, bb-dominate each other if there is a common cutpoint. A set L ⊆ B(G) is said to be a bb-dominating set (BBD set) if every block in B(G) - L is bb-dominated by some block in L. The bb-domination number γbb = γbb(G) is the cardinality of a minimum BBD-set of G. A vertex v and a block b are said to b-dominate each other if v is incident on the block b. Then vb-domination number γvb = γvb(G) (bv-domination number γbv = γbv(G)) is the minimum number of vertices (blocks) needed to b-dominate all the blocks (vertices) of G. In this paper we study the properties of these block domination parameters and establish a relation between these parameters giving an inequality chain consisting of nine parameters. [ABSTRACT FROM AUTHOR]