Sharp bounds for Zagreb indices of maximal outerplanar graphs

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we investigate the first and the second Zagreb indices of maximal outerplanar graph. We determine sharp upper and lower bounds for M ₁-, M ₂-values among the n-vertex maximal outerplanar graphs. As well we determine sharp upper and lower bounds of Zagreb indices for n-vertex outerplanar graphs (resp. maximal outerplanar graphs) with perfect matchings.     

New lower bounds for the second variable Zagreb index

The aim of this paper is to obtain new sharp inequalities for a large family of topological indices, including the second variable Zagreb index \(M_2^{\alpha }\), and to characterize the set of extremal graphs with respect to them. Our main results provide lower bounds on this family of topological indices involving just the minimum and the maximum degree of the graph. These inequalities are new even for the Randi?, the second Zagreb and the modified Zagreb indices.     

Minimum statuses of connected graphs with fixed maximum degree and order

The status of a vertex in a connected graph is the sum of distances between the vertex and all vertices. The minimum status of a connected graph is the minimum of statuses of all vertices of this graph. In this paper we obtain the sharp lower bound and the sharp upper bound on the minimum status of a connected graph with maximum degree k and order n. All the graphs attaining the lower bound are obtained, and a necessary condition is given for those graphs attaining the upper bound.     

On the mod sum number of H m,n

Let N denote the set of all positive integers. The sum graph G ⁺(S) of a finite subset S?N is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an mod sum graph if it is isomorphic to the sum graph of some S?Z _M \{0} and all arithmetic performed modulo M where M≥|S|+1. The mod sum number ρ(G) of G is the smallest number of isolated vertices which when added to G result in a mod sum graph. It is known that the graphs H _m,n (n>m≥3) are not mod sum graphs. In this paper we show that H _m,n are not mod sum graphs for m≥3 and n≥3. Additionally, we prove that ρ(H _m,3)=m for m≥3, H _m,n ∪ρK ₁ is exclusive for m≥3 and n≥4 and $m(n-1) \leq \rho(H_{m,n})\leq \frac{1}{2} mn(n-1)$ for m≥3 and n≥4.     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

Signed Roman domination in graphs

In this paper we continue the study of Roman dominating functions in graphs. A signed Roman dominating function (SRDF) on a graph G=(V,E) is a function f:V→{?1,1,2} satisfying the conditions that (i) the sum of its function values over any closed neighborhood is at least one and (ii) for every vertex u for which f(u)=?1 is adjacent to at least one vertex v for which f(v)=2. The weight of a SRDF is the sum of its function values over all vertices. The signed Roman domination number of G is the minimum weight of a SRDF in G. We present various lower and upper bounds on the signed Roman domination number of a graph. Let G be a graph of order n and size m with no isolated vertex. We show that $\gamma _{\mathrm{sR}}(G) \ge\frac{3}{\sqrt{2}} \sqrt{n} - n$ and that γ _sR(G)≥(3n?4m)/2. In both cases, we characterize the graphs achieving equality in these bounds. If G is a bipartite graph of order n, then we show that $\gamma_{\mathrm{sR}}(G) \ge3\sqrt{n+1} - n - 3$ , and we characterize the extremal graphs.     

Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.     

The total {k}-domatic number of wheels and complete graphs

Let k be a positive integer and let G be a graph with vertex set V(G). The total {k}-dominating function (T{k}DF) of a graph G is a function f from V(G) to the set {0,1,2,??,k}, such that for each vertex v??V(G), the sum of the values of all its neighbors assigned by f is at least k. A set {f ₁,f ₂,??,f _d } of pairwise different T{k}DFs of G with the property that $\sum_{i=1}^{d}f_{i}(v)\leq k$ for each v??V(G), is called a total {k}-dominating family (T{k}D family) of G. The total {k}-domatic number of a graph G, denoted by $d_{t}^{\{k\}}(G)$ , is the maximum number of functions in a T{k}D family. In this paper, we determine the exact values of the total {k}-domatic numbers of wheels and complete graphs, which answers an open problem of Sheikholeslami and Volkmann (J. Comb. Optim., 2010) and completes a result in the same paper.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.     

On total weight choosability of graphs

For a graph G with vertex set V and edge set E, a (k,k′)-total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)-total list assignment L of G, there exists a mapping f:V∪E→? such that f(y)∈L(y) for each y∈V∪E, and for any two adjacent vertices u and v, ∑ _y∈N(u) f(uy)+f(u)≠∑ _x∈N(v) f(vx)+f(v), then G is (k,k′)-total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)-total weight choosable, and every graph with no isolated edges is (1,3)-total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)-total weight choosable and (2,2)-total weight choosable. It is shown that s-degenerate graphs (with s≥2) are (1,2s)-total weight choosable. Hence planar graphs are (1,10)-total weight choosable, and outerplanar graphs are (1,4)-total weight choosable. We also give a combinatorial proof that wheels are (2,2)-total weight choosable, as well as (1,3)-total weight choosable.     

On the coefficients of the independence polynomial of graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let \(i_k = i_k(G)\) be the number of independent sets of cardinality k of G. The independence polynomial \(I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k\) defined first by Gutman and Harary has been the focus of considerable research recently, whereas \(i(G)=I(G, 1)\) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n,  the kth coefficient \(i_k\) is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number \(\omega \)) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number \(\chi \) (resp. vertex connectivity \(\kappa \)) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

Modified linear programming and class 0 bounds for graph pebbling

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.     

Max-coloring paths: tight bounds and extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G=(V,E) with vertex weights w such that $\sum_{i=1}^{k}\max_{v\in C_{i}}w(v_{i})$ is minimized, where C ₁,??,C _k are the various color classes. For general graphs, max-coloring is as hard as the classical vertex coloring problem, a special case of the former where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring skinny trees, a broad class of trees that includes paths and spiders. For these graphs, we show that max-coloring can be solved in time O(|V|+time for sorting the vertex weights). When vertex weights are real numbers, we show a matching lower bound of ??(|V|log?|V|) in the algebraic computation tree model.     

Further results on the reciprocal degree distance of graphs

The reciprocal degree distance of a simple connected graph \(G=(V_G, E_G)\) is defined as \(\bar{R}(G)=\sum _{u,v \in V_G}(\delta _G(u)+\delta _G(v))\frac{1}{d_G(u,v)}\), where \(\delta _G(u)\) is the vertex degree of \(u\), and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\). The reciprocal degree distance is an additive weight version of the Harary index, which is defined as \(H(G)=\sum _{u,v \in V_G}\frac{1}{d_G(u,v)}\). In this paper, the extremal \(\bar{R}\)-values on several types of important graphs are considered. The graph with the maximum \(\bar{R}\)-value among all the simple connected graphs of diameter \(d\) is determined. Among the connected bipartite graphs of order \(n\), the graph with a given matching number (resp. vertex connectivity) having the maximum \(\bar{R}\)-value is characterized. Finally, sharp upper bounds on \(\bar{R}\)-value among all simple connected outerplanar (resp. planar) graphs are determined.     

Exact and approximation algorithms for?the?complementary maximal strip recovery problem

Given two genomic maps G ₁ and G ₂ each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G ₁ and G ₂ such that the resultant subsequences, denoted as $G_{1}^{*}$ and $G_{2}^{*}$ , can be partitioned into the same set of maximal substrings of length greater than or equal to two. Such substrings can occur in the reversal and negated form. The complementary maximal strip recovery (CMSR) problem is to delete the minimum number of markers from both G ₁ and G ₂ for the same purpose, with its optimization goal exactly complementary to maximizing the total number of gene markers retained in the final maximal substrings. Both MSR and CMSR have been shown NP-hard and APX-hard. A?4-approximation algorithm is known for the MSR problem, but no constant ratio approximation algorithm for CMSR. In this paper, we present an O(3 ^k n ²)-time fixed-parameter tractable (FPT) algorithm, where k is the size of the optimal solution, and a 3-approximation algorithm for the CMSR problem.     

A parameterized perspective on packing paths of length two

We study (vertex-disjoint) packings of paths of length two (i.e., of P ₂’s) in graphs under a parameterized perspective. Starting from a maximal P ₂-packing ℘ of size j we use extremal combinatorial arguments for determining how many vertices of ℘ appear in some P ₂-packing of size (j+1) (if such a packing exists). We prove that one can ‘reuse’ 2.5j vertices. We also show that this bound is asymptotically sharp. Based on a WIN-WIN approach, we build an algorithm which decides, given a graph, if a P ₂-packing of size at least k exists in time O^*(2.448^3k)\mathcal{O}^{*}(2.448^{3k}) .     

Note on the hardness of generalized connectivity

Let G be a nontrivial connected graph of order n and let k be an integer with 2??k??n. For a set S of k vertices of G, let ??(S) denote the maximum number ? of edge-disjoint trees T ₁,T ₂,??,T _? in G such that V(T _i )??V(T _j )=S for every pair i,j of distinct integers with 1??i,j???. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by ?? _k (G), of G is defined by ?? _k (G)=min{??(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?? ₂(G)=??(G), where ??(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of determining the generalized connectivity of a graph. At first, we obtain that for two fixed positive integers k ₁ and k ₂, given a graph G and a k ₁-subset S of V(G), the problem of deciding whether G contains k ₂ internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k ₁ is a fixed integer of at least 4, but k ₂ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k ₂ is a fixed integer of at least 2, but k ₁ is not a fixed integer, we show that the problem also becomes NP-complete.     

The decycling number of outerplanar graphs

For a graph G, let τ(G) be the decycling number of G and c(G) be the number of vertex-disjoint cycles of G. It has been proved that c(G)≤τ(G)≤2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if τ(G)=c(G) and upper-extremal if τ(G)=2c(G). In this paper, we provide a necessary and sufficient condition for an outerplanar graph being upper-extremal. On the other hand, we find a class $\mathcal{S}$ of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all $S\in \mathcal{S}$ , then G is lower-extremal.     

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ?-colourings of G is connected and has diameter O(|V|²), for all ?≥k+1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k=2. Moreover, we prove that for each k≥2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|²).