A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

Results on the Grundy chromatic number of graphs

Given a graph G, by a Grundy k-coloring of G we mean any proper k-vertex coloring of G such that for each two colors i and j, i<j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ(G) and called Grundy (chromatic) number of G. We first discuss the fixed-parameter complexity of determining Γ(G)?k, for any fixed integer k and show that it is a polynomial time problem. But in general, Grundy number is an NP-complete problem. We show that it is NP-complete even for the complement of bipartite graphs and describe the Grundy number of these graphs in terms of the minimum edge dominating number of their complements. Next we obtain some additive Nordhaus-Gaddum-type inequalities concerning Γ(G) and Γ(G^c), for a few family of graphs. We introduce well-colored graphs, which are graphs G for which applying every greedy coloring results in a coloring of G with χ(G) colors. Equivalently G is well colored if Γ(G)=χ(G). We prove that the recognition problem of well-colored graphs is a coNP-complete problem.     

Chromatic characterization of biclique covers

A biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0-1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer.     

On the complexity of the independent set problem in triangle graphs

We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G−I, there is a vertex w∈I such that {u,v,w} is a triangle in G. We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are NP-complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P=NP.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Covering graphs with matchings of fixed size

Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum[m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive[m]-factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive[m]-index and denoted by . In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.     

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.     

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.     

Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

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.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

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.     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

On the minimum real roots of the adjoint polynomial of a graph

For a graph G, we denote by h(G,x) the adjoint polynomial of G. Let β(G) denote the minimum real root of h(G,x). In this paper, we characterize all the connected graphs G with .     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

A polynomial algorithm for finding (<Emphasis Type="Italic">g,f</Emphasis>)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). A (g, f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

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.