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.     

The multiple originator broadcasting problem in graphs

Given a graph G and a vertex subset S of V(G), the broadcasting time with respect toS, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by b_k(G), is defined by b_k(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph G and two vertex subsets S, S^′ of V(G), define , d(S,S^′)=min{d(u,v)|u∈S, v∈S^′}, and for all v∈V(G). For all k, 1?k?|V(G)|, the k-radius of G, denoted by r_k(G), is defined as r_k(G)=min{d(G,S)|S⊆V(G), |S|=k}.In this paper, we study the relation between the k-radius and the k-broadcasting numbers of graphs. We also give the 2-radius and the 2-broadcasting numbers of the grid graphs, and the k-broadcasting numbers of the complete n-partite graphs and the hypercubes.     

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.     

On multicolour noncomplete Ramsey graphs of star graphs

Given graphs , where k≥2, the notation

     

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₃.     

Finding monotone paths in edge-ordered graphs

An edge-ordering of a graph G=(V,E) is a one-to-one function f from E to a subset of the set of positive integers. A path P in G is called an f-ascent if f increases along the edge sequence of P. The heighth(f) of f is the maximum length of an f-ascent in G.In this paper we deal with computational problems concerning finding ascents in graphs. We prove that for a given edge-ordering f of a graph G the problem of determining the value of h(f) is NP-hard. In particular, the problem of deciding whether there is an f-ascent containing all the vertices of G is NP-complete. We also study several variants of this problem, discuss randomized and deterministic approaches and provide an algorithm for the finding of ascents of order at least k in graphs of order n in running time O(4^kn^O(1)).     

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.     

Distance-two labellings of Hamming graphs

Let j≥k≥0 be integers. An ?-L(j,k)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…,?} such that |?(u)−?(v)|≥j if u,v are adjacent and |?(u)−?(v)|≥k if they are distance two apart. Let λ_j,k(G) be the smallest integer ? such that G admits an ?-L(j,k)-labelling. Define to be the smallest ? if G admits an ?-L(j,k)-labelling with ?(V)={0,1,2,…,?} and ∞ otherwise. An ?-cyclic L(j,k)-labelling is a mapping ?:V→Z_? such that |?(u)−?(v)|_?≥j if u,v are adjacent and |?(u)−?(v)|_?≥k if they are distance two apart, where |x|_?=min{x,?−x} for x between 0 and ?. Let σ_j,k(G) be the smallest ?−1 of such a labelling, and define similarly to . We determine λ_2,0, , σ_2,0 and for all Hamming graphs K_q1□K_q2□?□K_qd (d≥2, q₁≥q₂≥?≥q_d≥2) and give optimal labellings, with the only exception being for q≥4. We also prove the following “sandwich theorem”: If q₁ is sufficiently large then for any graph G between K_q1□K_q2 and K_q1□K_q2□?□K_qd, and moreover we give a labelling which is optimal for these eight invariants simultaneously.