An $$O(|E(G)|^2)$$ algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

A graph \(G=(V,E)\) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.     

A simplex like approach based on star sets for recognizing convex-QP adverse graphs

A graph \(G\) with convex-\(QP\) stability number (or simply a convex-\(QP\) graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic program, say \(P(G)\). There are polynomial-time procedures to recognize convex-\(QP\) graphs, except when the graph \(G\) is adverse or contains an adverse subgraph (that is, a non complete graph, without isolated vertices, such that the least eigenvalue of its adjacency matrix and the optimal value of \(P(G)\) are both integer and none of them changes when the neighborhood of any vertex of \(G\) is deleted). In this paper, from a characterization of convex-\(QP\) graphs based on star sets associated to the least eigenvalue of its adjacency matrix, a simplex-like algorithm for the recognition of convex-\(QP\) adverse graphs is introduced.     

Coupon coloring of some special graphs

Let G be a graph without isolated vertices. A k-coupon coloring of G is a k-coloring of G such that the neighborhood of every vertex of G contains vertices of all colors from \([k] =\{1, 2, \ldots , k\}\), which was recently introduced by Chen, Kim, Tait and Verstraete. The coupon coloring number \(\chi _c(G)\) of G is the maximum k for which a k-coupon coloring exists. In this paper, we mainly study the coupon coloring of some special classes of graphs. We determine the coupon coloring numbers of complete graphs, complete k-partite graphs, wheels, cycles, unicyclic graphs, bicyclic graphs and generalised \(\Theta \)-graphs.     

Rainbow connection numbers of Cayley graphs

An edge colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc-number for short, of a graph \({\varGamma }\), is the smallest number of colors that are needed in order to make \({\varGamma }\) rainbow connected. In this paper, we give a method to bound the rc-numbers of graphs with certain structural properties. Using this method, we investigate the rc-numbers of Cayley graphs, especially, those defined on abelian groups and on dihedral groups.     

Fractional matching preclusion of graphs

Let F be an edge subset and \(F^{\prime }\) a subset of edges and vertices of a graph G. If \(G-F\) and \(G-F^{\prime }\) have no fractional perfect matchings, then F is a fractional matching preclusion (FMP) set and \(F^{\prime }\) is a fractional strong MP (FSMP) set of G. The FMP (FSMP) number of G is the minimum size of FMP (FSMP) sets of G. In this paper, the FMP number and the FSMP number of Petersen graph, complete graphs and twisted cubes are obtained, respectively.     

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.     

On maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.     

Approximation for vertex cover in $$\beta $$-conflict graphs

Conflict graph is a union of finite given sets of disjoint complete multipartite graphs. Vertex cover on this kind of graph is used first to model data inconsistency problems in database application. It is NP-complete if the number of given sets r is fixed, and can be approximated within \(2-\frac{1}{2^r}\) (Miao et al. in Proceedings of the 9th international conference on combinatorial optimization and applications, vol 9486. COCOA 2015, New York. Springer, New York, pp 395–408, 2015). This paper shows a better algorithm to improve the approximation for dense cases. If the ratio of vertex not belongs to any wheel complete multipartite graph is no more than \(\beta <1\), then our algorithm will provide a \((1+\beta +\frac{1-\beta }{k})\)-approximation, where k is a parameter related to degree distribution of wheel complete multipartite graph.     

Recognition of overlap graphs

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings \(s_{i}\) and \(s_{j}\) , their overlap string is defined as the longest string \(v\) such that \(s_{i} = uv\) and \(s_{j} = vw\) , for some non empty strings \(u,w\) , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph \(G\) , the algorithm constructs a set of strings that has \(G\) as its overlap graph, or decides that this is not possible.     

Finding disjoint paths on edge-colored graphs: more tractability results

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.     

Maximum cardinality neighbourly sets in quadrilateral free graphs

Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (Discret Appl Math 118:239–248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an \(O(n^{11})\) algorithm for the same, here n is the number of vertices in the graph, (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in \(O(n^5)\) running time). In this paper we propose an \(O(n^2)\) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph.     

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

Parity and strong parity edge-colorings of graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. A parity edge-coloring (respectively, strong parity edge-coloring) is an edge-coloring in which there is no nontrivial parity path (respectively, open parity walk). The parity edge-chromatic number p(G) (respectively, strong parity edge-chromatic number $\widehat{p}(G)$ ) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that $\widehat{p}(G) \ge p(G) \ge \chi'(G) \ge \Delta(G)$ for any graph G. In this paper, we determine $\widehat{p}(G)$ and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine $\widehat{p}(K_{m,n})$ and p(K _m,n ) for m≤n with n≡0,?1,?2 (mod 2^?lg?m?).     

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.     

Disconnected $$g_c$$-critical graphs

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on \(g_c\)-colorings of simple graphs. In this article, disconnected \(g_c\)-critical graphs are studied firstly and their structure characteristics are depicted.     

Embeddings into almost self-centered graphs of given radius

A graph is almost self-centered (ASC) if all but two of its vertices are central. An almost self-centered graph with radius r is called an r-ASC graph. The r-ASC index \(\theta _r(G)\) of a graph G is the minimum number of vertices needed to be added to G such that an r-ASC graph is obtained that contains G as an induced subgraph. It is proved that \(\theta _r(G)\le 2r\) holds for any graph G and any \(r\ge 2\) which improves the earlier known bound \(\theta _r(G)\le 2r+1\). It is further proved that \(\theta _r(G)\le 2r-1\) holds if \(r\ge 3\) and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that \(\theta _3(G)\in \{3,4\}\) if G has diameter 2 and for several classes of graphs of diameter 2 the exact value of the 3-ASC index is obtained. For instance, if a graph G of diameter 2 does not contain a diametrical triple, then \(\theta _3(G) = 4\). The 3-ASC index of paths of order \(n\ge 1\), cycles of order \(n\ge 3\), and trees of order \(n\ge 10\) and diameter \(n-2\) are also determined, respectively, and several open problems proposed.     

Disjunctive total domination in graphs

Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, \(\gamma _t(G)\). A set \(S\) of vertices in \(G\) is a disjunctive total dominating set of \(G\) if every vertex is adjacent to a vertex of \(S\) or has at least two vertices in \(S\) at distance \(2\) from it. The disjunctive total domination number, \(\gamma ^d_t(G)\), is the minimum cardinality of such a set. We observe that \(\gamma ^d_t(G) \le \gamma _t(G)\). We prove that if \(G\) is a connected graph of order \(n \ge 8\), then \(\gamma ^d_t(G) \le 2(n-1)/3\) and we characterize the extremal graphs. It is known that if \(G\) is a connected claw-free graph of order \(n\), then \(\gamma _t(G) \le 2n/3\) and this upper bound is tight for arbitrarily large \(n\). We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if \(G\) is a connected claw-free graph of order \(n > 14\), then \(\gamma ^d_t(G) \le 4n/7\) and we characterize the graphs achieving equality in this bound.