The clique operator on circular-arc graphs

A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKⁱ(G) of G is defined by K⁰(G)=G and Kⁱ⁺¹(G)=K(Kⁱ(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

Some complexity problems on single input double output controllers

We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P₃-partition of the graph G. A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P₃-partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P₃-partition. It is also proved that the decision problem on two particular graph classes — defined in terms of forbidden subgraphs — remains NP-complete, but is polynomially solvable on the intersection of those two classes. The polynomial-time solvability of some further related problems is shown, too.     

Triangle path transit functions, betweenness and pseudo-modular graphs

The geodesic and induced path transit functions are the two well-studied interval functions in graphs. Two important transit functions related to the geodesic and induced path functions are the triangle path transit functions which consist of all vertices on all u,v-shortest (induced) paths or all vertices adjacent to two adjacent vertices on all u,v-shortest (induced) paths, for any two vertices u and v in a connected graph G. In this paper we study the two triangle path transit functions, namely the I^Δ and J^Δ on G. We discuss the betweenness axioms, for both triangle path transit functions. Also we present a characterization of pseudo-modular graphs using the transit function I^Δ by forbidden subgraphs.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

Triangular line graphs and word sense disambiguation

Linguists often represent the relationships between words in a collection of text as an undirected graph G=(V,E), where V is the vocabulary and vertices are adjacent in G if and only if the words that they represent co-occur in a relevant pattern in the text. Ideally, the words with similar meanings give rise to the vertices of a component of the graph. However, many words have several distinct meanings, preventing components from characterizing distinct semantic fields. This paper examines how the structural properties of triangular line graphs motivate the use of a clustering coefficient on the triangular line graph, thereby helping to identify polysemous words. The triangular line graph of G, denoted by T(G), is the subgraph of the line graph of G where two vertices are adjacent if the corresponding edges in G belong to a K₃.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.     

Representation of graphs by OBDDs

Recently, it has been shown in a series of works that the representation of graphs by Ordered Binary Decision Diagrams (OBDDs) often leads to good algorithmic behavior. However, the question for which graph classes an OBDD representation is advantageous, has not been investigated, yet. In this paper, the space requirements for the OBDD representation of certain graph classes, specifically cographs, several types of graphs with few P₄s, unit interval graphs, interval graphs and bipartite graphs are investigated. Upper and lower bounds are proven for all these graph classes and it is shown that in most (but not all) cases a representation of the graphs by OBDDs is advantageous with respect to space requirements.     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and f_s(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients f_s(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before.     

On disconnected cuts and separators

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V?U)∪{u} is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.     

On the complexity of the multicut problem in bounded tree-width graphs and digraphs

Given an edge- or vertex-weighted graph or digraph and a list of source-sink pairs, the minimum multicut problem consists in selecting a minimum weight set of edges or vertices whose removal leaves no path from each source to the corresponding sink. This is a classical NP-hard problem, and we show that the edge version becomes tractable in bounded tree-width graphs if the number of source-sink pairs is fixed, but remains NP-hard in directed acyclic graphs and APX-hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be NP-hard in unweighted cacti of bounded degree and bounded path-width.     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique.     

The induced path function, monotonicity and betweenness

The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský [20]. Surprisingly, Nebeský [23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if w∈J(u,v), with w≠u, implies u∉J(w,v) and x∈J(u,v) implies J(u,x)⊆J(u,v). It is monotone if x,y∈J(u,v) implies J(x,y)⊆J(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.     

Precoloring extension on unit interval graphs

In the precoloring extension problem a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. Answering an open question of Hujter and Tuza [Precoloring extension. III. Classes of perfect graphs, Combin. Probab. Comput. 5 (1) (1996) 35-56], we show that the precoloring extension problem is NP-complete on unit interval graphs.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

On the 3-restricted edge connectivity of permutation graphs

An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.