Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

This paper studies the graphs for which the linear relaxation of the 2-connected spanning subgraph polyhedron has integer or half-integer extreme points. These graphs are called quasi-integer. For these graphs, the linear relaxation of the k-edge connected spanning subgraph polyhedron is integer for all k=4r, r≥1. The class of quasi-integer graphs is closed under minors and contains for instance the class of series-parallel graphs. We discuss some structural properties of graphs which are minimally non quasi-integer graphs, then we examine some basic operations which preserve the quasi-integer property. Using this, we show that the subdivisions of wheels are quasi-integer.     

Vertex and Tree Arboricities of Graphs

This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.     

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.     

Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs. Research supported by NSFC.     

Fibonacci index and stability number of graphs: a polyhedral study

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.     

The thickness of the complete multipartite graphs and the join of graphs

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

The <Emphasis Type="Italic">p</Emphasis>-maxian problem on block graphs

This paper deals with the p-maxian problem on block graphs with unit edge length. It is shown that the two points with maximum distance provide an optimal solution for the 2-maxian problem of block graphs except for K ₃. It can easily be extended to the p-maxian problem of block graphs. So we solve the p-maxian problem on block graphs in linear time.     

Efficient identifications of structural similarities for graphs

Measuring and detecting graph similarities is an important topic with numerous applications. Early algorithms often incur quadratic time or higher, making them unsuitable for graphs of very large scales. Motivated by the cooling process of an object in a thermodynamic system, we devise a new method for measuring graph similarities that can be carried out in linear time. Our algorithm, called Random Walker Termination (RWT), employs a large number of random walkers to capture the structure of a given graph using termination rates in a time sequence. To verify the effectiveness of the RWT algorithm, we use three major graph models, namely, the Erd?s-Rényi random graphs, the Watts-Strogatz small-world graphs, and the Barabási-Albert preferential-attachment graphs, to generate graphs of different sizes. We show that the RWT algorithm performs well for graphs generated by these models. Our experiment results agree with the actual similarities of generated graphs. Using self-similarity tests, we show that RWT is sufficiently stable to generate consistent results. We use the graph edge rerouting test and the cross model test to demonstrate that RWT can effectively identify structural similarities between graphs.     

The second largest number of maximal independent sets in connected graphs with at most one cycle

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n??4 with at most one cycle. We also characterize those extremal graphs achieving these values.     

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n ^o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

Efficient algorithms for supergraph query processing on graph databases

We study the problem of processing supergraph queries on graph databases. A graph database D is a large set of graphs. A supergraph query q on D is to retrieve all the graphs in D such that q is a supergraph of them. The large number of graphs in databases and the NP-completeness of subgraph isomorphism testing make it challenging to efficiently processing supergraph queries. In this paper, a new approach to processing supergraph queries is proposed. Specifically, a method for compactly organizing graph databases is first presented. Common subgraphs of the graphs in a database are stored only once in the compact organization of the database, in order to reduce the overall cost of subgraph isomorphism testings from the stored graphs to queries during query processing. Then, an exact algorithm and an approximate algorithm for generating the significant feature set with optimal order are proposed, followed by the algorithms for indices construction on graph databases. The optimal order on the feature set is to reduce the number of subgraph isomorphism testings during query processing. Based on the compact organization of graph databases, a novel algorithm for testing subgraph isomorphisms from multiple graphs to one graph is presented. Finally, based on all the above techniques, a query processing method is proposed. Analytical and experimental results show that the proposed algorithms outperform the existing similar algorithms by one to two orders of magnitude.     

A combinatorial proof for the circular chromatic number of Kneser graphs

Chen (J Combin Theory A 118(3):1062–1071, 2011) confirmed the Johnson–Holroyd–Stahl conjecture that the circular chromatic number of a Kneser graph is equal to its chromatic number. A shorter proof of this result was given by Chang et al. (J Combin Theory A 120:159–163, 2013). Both proofs were based on Fan’s lemma (Ann Math 56:431–437, 1952) in algebraic topology. In this article we give a further simplified proof of this result. Moreover, by specializing a constructive proof of Fan’s lemma by Prescott and Su (J Combin Theory A 111:257–265, 2005), our proof is self-contained and combinatorial.     

Strongly chordal and chordal bipartite graphs are sandwich monotone

A graph class is sandwich monotone if, for every pair of its graphs G ₁=(V,E ₁) and G ₂=(V,E ₂) with E ₁⊂E ₂, there is an ordering e ₁,…,e _k of the edges in E ₂∖E ₁ such that G=(V,E ₁∪{e ₁,…,e _i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.     

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

In this paper, we study the complexity and the approximation of the k most vital edges (nodes) and min edge (node) blocker versions for the minimum spanning tree problem (MST). We show that the k most vital edges MST problem is NP-hard even for complete graphs with weights 0 or 1 and 3-approximable for graphs with weights 0 or 1. We also prove that the k most vital nodes MST problem is not approximable within a factor n ^1?? , for any ?>0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1. Furthermore, we show that the min edge blocker MST problem is NP-hard even for complete graphs with weights 0 or 1 and that the min node blocker MST problem is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1.     

Improved approximation for spanning star forest in dense graphs

A spanning subgraph of a graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1. The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning star forest problem is to find the maximum-size spanning star forest of a given graph. In this paper, we study the spanning star forest problem on c-dense graphs, where for any fixed c∈(0,1), a graph of n vertices is called c-dense if it contains at least cn ²/2 edges. We design a $(\alpha+(1-\alpha)\sqrt{c}-\epsilon)$ -approximation algorithm for spanning star forest in c-dense graphs for any ?>0, where $\alpha=\frac{193}{240}$ is the best known approximation ratio of the spanning star forest problem in general graphs. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with c-dense graphs. We also prove that, for any constant c∈(0,1), approximating spanning star forest in c-dense graphs is APX-hard. We then demonstrate that for weighted versions (both node- and edge-weighted) of this problem, we cannot get any approximation algorithm with strictly better performance guarantee on c-dense graphs than on general graphs. Finally, we give strong inapproximability results for a closely related problem, namely the minimum dominating set problem, restricted on c-dense graphs.     

The densest <Emphasis Type="Italic">k</Emphasis>-subgraph problem on clique graphs

The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques. M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources. V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821.     

Compact labelings for efficient first-order model-checking

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is nicely locally clique-width-decomposable. This notion generalizes that of a nicely locally tree-decomposable class. The graphs of such classes can be covered by graphs of bounded clique-width with limited overlaps. We also consider such labelings for bounded first-order formulas on graph classes of bounded expansion. Some of these results are extended to counting queries.     

Labelling algorithms for paired-domination problems in block and interval graphs

Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math. 155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs.