Narrow Results

Let $H=(V,E)$ be an undirected, planar, non-trivial, connected, and simple graph, where the sets $V$ and $E$ are respectively the vertex and edge sets for $H$. The cardinalities of the sets $E$ and $V$ (i.e., $\left|E\right|$ and $\left|V\right|$) are referred to be the size and order of $H$. A subset $J=\{{\alpha }_1,{\alpha }_2,{\alpha }_3,\dots ,{\alpha }_p\}$ (ordered vertices) of $V$ is termed as a resolving set [edge resolving set (ERS)] for $H$ if for every two distinct vertices $v_i,v_j\in V(H)$ [edges $e_i,e_j\in E(H)$], there is a vertex ${\alpha }_i\in J$ such that $d({\alpha }_i,v_i)\ne d({\alpha }_i,v_j)$ [$d({\alpha }_i,e_i)\ne d({\alpha }_i,e_j)$]. A resolving set (ERS) consisting of the minimum number of vertices is called the metric basis [edge metric basis (EMB)] for $H$ and the cardinality of metric basis (EMB) set is its metric dimension (edge metric dimension), represented by $\mathrm{\text{dim}}(H)$ [$\mathrm{\text{edim}}(H)$]. In this paper, we initiate the study of edge and vertex resolvability parameters for a novel class of planar graphs. Further, we will show that the planar graph possesses an independent minimum vertex and the edge resolving sets having cardinality 3 or 4.

For a non-trivial connected graph $\mathrm{\Gamma }=\mathrm{\Gamma }(V,E)$, an ordered subset $U$ of vertices $resolves$ any pair of different vertices $k_1,k_2\in V$, if $d(k,k_1)\ne d(k,k_2)$ for some $k\in U$. Such a set $U$ is said to be a resolving set (RS) for $\mathrm{\Gamma }$ and the smallest cardinality of $U$ is called the $metric$$dimension$ of $\mathrm{\Gamma }$. A RS $U^{\ast }$ for $\mathrm{\Gamma }$ is said to be fault-tolerant resolving set (FTRS) if the property of resolving $\mathrm{\Gamma }$ holds by $U^{\ast }-\{k\}$ for every $k$ in $U^{\ast }$. The minimum cardinality of such a set $U^{\ast }$ is called the fault-tolerant metric dimension (FTMD) of $\mathrm{\Gamma }$. It is generally denoted by ${\mathrm{\text{dim}}}_{ft}(\mathrm{\Gamma })$. In this paper, the notion of FTRS and that of FTMD have been determined for two complex families of infinite convex polytope graphs, which are obtained by joining certain copies of the prism graph together with an antiprism graph. For these two families of planar graph (viz., $D_m^k$ & $E_m^k$), we investigate several properties as well as we compare their metric and FTMD.

A representation for a set is defined to be symmetric if the space required for the representation of the set is the same as the space required for representation of the set's complement. The use of symmetric representation is shown to be important when studying the time complexity of algorithms. A symmetric data structure called a flip list is defined, and it is employed for the Clique, Independent Set, and Vertex Cover problems in a case study. The classic reductions among these problems require the complement of either a graph's edge set or a subset of its vertices. Flip lists can be complemented in constant time with no increase in space. When a flip list is used to represent the edge set of a graph, Clique, Independent Set, and Vertex Cover are shown to have identical (and strongly exponential) time complexity when the classical complexity parameter of input length is used. On the other hand, when a flip list is used to represent a set of numbers as input for the Partition problem, an algorithm can be built that retains strongly sub-exponential time complexity. This provides new evidence with respect to which NP- complete problems should be classified as sub-exponential. Symmetric representation has the advantage of space efficiency, at most linear-time and space complement operations, and symmetry in representing sparse and dense sets. These features can have a significant impact on complexity studies.

Complementary prism graphs arise from the disjoint union of a graph $G$ and its complement $Ḡ$ by adding the edges of a perfect matching joining pairs of corresponding vertices of $G$ and $Ḡ$. Classical graph problems such as Clique and Independent Set were proved to be NP-complete on such a class of graphs. In this work, we study the complexity of both problems on complementary prism graphs from the parameterized complexity point of view. First, we prove that both problems admit a kernel and therefore are fixed-parameter tractable (FPT) when parameterized by the size of the solution, $k$. Then, we show that ${k}$-Clique and ${k}$-Independent Set on complementary prisms do not admit polynomial kernel when parameterized by $k$, unless $NP\subseteq coNP/poly$. Furthermore, we address the $2$-Contamination problem in the context of complementary prisms. This problem consists in completely contaminating a given graph $G$ using a minimum set of initially infected vertices. For a vertex to be contaminated, it is enough that at least two of its neighbors are contaminated. The propagation of the contamination follows this rule until no more vertex can be contaminated. It is known that the minimum set of initially contaminated vertices necessary to contaminate a complementary prism of connected graphs $G$ and $Ḡ$ has cardinality at most $5$. In this paper, we show that the tight upper bound for this invariant on complementary prisms is $3$, improving a result of Duarte et al. (2017).

This paper presents an extraction and expansion approach for the graph coloring problem. The extraction phase transforms a large graph into a sequence of progressively smaller graphs by removing large independent sets from the graph. The expansion phase starts by generating an approximate coloring for the smallest graph in the sequence. Then it expands the smallest graph by progressively adding back the extracted independent sets and determine a coloring for each intermediate graph. To color each graph, a simple perturbation based tabu search algorithm is used. The proposed approach is evaluated on the DIMACS challenge benchmarks showing competitive results in comparison with the state-of-the-art methods.

Independent set games are cooperative games defined on graphs, where players are edges and the value of a coalition is the maximum size of independent sets in the subgraph defined by the coalition. In this paper, we study population monotonic allocation schemes for independent set games. For independent set games introduced by Deng et al. [X. Deng, T. Ibaraki and H. Nagamochi (1999). Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3), 751–766], we provide a combinatorial characterization for population monotonic allocation schemes in convex instances. For independent set games introduced by Xiao et al. [H. Xiao, Y. Wang and Q. Fang (2021). On the convexity of independent set games. Discrete Applied Mathematics, 291, 271–276], we prove the equivalence of convexity, population monotonicity and balancedness.

We study the problem of reconstructing convex polygons and convex polyhedra given the number of visible edges and visible faces in some orthogonal projections. In 2D, we find necessary and sufficient conditions for the existence of a feasible polygon of size N and give an algorithm to construct one, if it exists. When N is not known, we give an algorithm to find the maximum and minimum sizes of a feasible polygon. In 3D, when the directions are covered by a single plane we show that a feasible polyhedron can be constructed from a feasible polygon. We also give an algorithm to construct a feasible polyhedron when the directions are covered by two planes. Finally, we show that the problem becomes NP-hard when the directions are covered by three or more planes.

In this paper, we give a lower bound of the number of maximal independent sets in a graph $G$ in terms of the Castelnuovo–Mumford regularity of its edge ideal. We also find two classes of graphs achieving this minimum value.

Large volumes of structured and semi-structured data are being generated every day. Processing this large amount of data and extracting important information is a challenging task. The goal of an automatic text summarization is to preserve the key information and the overall meaning of the article to be summarized. In this paper, a graph-based approach is followed to generate an extractive summary, where sentences of the article are considered as vertices, and weighted edges are introduced based on the cosine similarities among the vertices. A possible subset of maximal independent sets of vertices of the graph is identified with the assumption that adjacent vertices provide sentences with similar information. The degree centrality and clustering coefficient of the vertices are used to compute the score of each of the maximal independent sets. The set with the highest score provides the final summary of the article. The proposed method is evaluated using the benchmark BBC News data to demonstrate its effectiveness and is applied to the COVID-19 Twitter data to express its applicability in topic modeling. Both the application and comparative study with other methods illustrate the efficacy of the proposed methodology.

In this paper, the resolving parameters such as metric dimension and partition dimension for the nonzero component graph, associated to a finite vector space, are discussed. The exact values of these parameters are determined. It is derived that the notions of metric dimension and locating-domination number coincide in the graph. Independent sets, introduced by Boutin [Determining sets, resolving set, and the exchange property, Graphs Combin.25 (2009) 789–806], are studied in the graph. It is shown that the exchange property holds in the graph for minimal resolving sets with some exceptions. Consequently, a minimal resolving set of the graph is a basis for a matroid with the set $V$ of nonzero vectors of the vector space as the ground set. The matroid intersection problem for two matroids with $V$ as the ground set is also solved.

A vertex set D of a connected graph G is a (k, r)-connected dominating set ((k, r)-CDS) if every vertex in V(G)\D is at most r-hops away from at least k vertices in D. Finding a minimum (k, r)-CDS has wireless sensor network as its background. In this paper, we give two approximation algorithms to compute a minimum (k, r)-CDS, which improves previous works in regard of performance ratio.

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.

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

Let $m>1$ be an integer, and let $I{({\mathbb{Z}}_m)}^{\ast }$ be the set of all non-zero proper ideals of ${\mathbb{Z}}_m$. The intersection graph of ideals of ${\mathbb{Z}}_m$, denoted by $G({\mathbb{Z}}_m)$, is a graph with the vertex set $I{({\mathbb{Z}}_m)}^{\ast }$ and two distinct vertices $I,J\in I{({\mathbb{Z}}_m)}^{\ast }$ are adjacent if and only if $I\cap J\ne 0$. Let $n>1$ be an integer and ${\mathbb{Z}}_n$ be a ${\mathbb{Z}}_m$-module. In this paper, we study a kind of graph structure of ${\mathbb{Z}}_m$, denoted by $G_n({\mathbb{Z}}_m)$. It is the undirected graph with the vertex set $I{({\mathbb{Z}}_m)}^{\ast }$, and two distinct vertices $I$ and $J$ are adjacent if and only if $I{\mathbb{Z}}_n\cap J{\mathbb{Z}}_n\ne 0$. Clearly, $G_m({\mathbb{Z}}_m)=G({\mathbb{Z}}_m)$. Let $m=p_1^{{\alpha }_1}\cdots p_s^{{\alpha }_s}$ and $n=p_1^{{\beta }_1}\cdots p_s^{{\beta }_s}$, where $p_i$’s are distinct primes, ${\alpha }_i$’s are positive integers, ${\beta }_i$’s are non-negative integers, and $0\le {\beta }_i\le {\alpha }_i$ for $i=1,\dots ,s$ and let $S=\{1,\dots ,s\}$, $S^{\prime }=\{i\in S:{\beta }_i\ne 0\}$. The cardinality of $S^{\prime }$ is denoted by $s^{\prime }$. Also, let $\alpha (G_n({\mathbb{Z}}_m))$, $\gamma (G_n({\mathbb{Z}}_m))$ and $𝔄$ denote the independence number, the domination number and the set of all isolated vertices of $G_n({\mathbb{Z}}_m)$, respectively. We prove that $gr(G_n({\mathbb{Z}}_m))\in \{3,\infty \}$ and we show that if $G_n({\mathbb{Z}}_m)$ is not a null graph, then

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(3m,2m)=4$, $A(\frac{m(m+1)}{2},2m-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.

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\subseteq E\setminus F$, there exists an edge $e\in F$ such that the edge-induced subgraph $〈L\cup \{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 ${\gamma }_{\mathrm{\text{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 ${\gamma }_l(G)={\gamma }_{\mathrm{\text{lsd}}}(G)$ where ${\gamma }_l(G)$ is the line domination number of $G$.

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 $\alpha$-set in $G$. An independent set $D\subset V(G)-A$ is called an inverse independent set with respect to $A$. The inverse independence number ${\alpha }^{-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.

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.

A set $S\subseteq 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 ${\gamma }_{\mathrm{\text{it}}}(G)$. In this paper we prove that for trees $T$, ${\gamma }_{\mathrm{\text{it}}}(T)$ is bounded above by $\lceil \frac{n}{2}\rceil$ 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.

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\in \mathbb{N}$ 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\ge 8$ and $Z_s$, where $s\ge 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.