A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs

A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ _u∈V f(u). The Roman domination number γ_R(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ _k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γ_R(H)/3.     

The k-neighbourhood-covering problem on interval graphs

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ? V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.     

Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

Irregular Total Labellings of Generalized Petersen Graphs

The total edge irregularity strength tes(G) and total vertex irregularity strength tvs(G) are invariants analogous to irregular strength s(G) of a graph G for total labellings. Bača et al. (Discrete Math. 307:1378–1388, 2007) determined the bounds and precise values for some families of graphs concerning these parameters. In this paper, we show the exact values of the total edge irregularity strength and total vertex irregularity strength of generalized Petersen graphs P(n,k).     

Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

For an ordered subset W= w₁, w₂,?…?w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂),?…?, d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.     

The linear programming approach to the Randić index

Let G(k, n) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k. The Randi? index of a graph G is: , where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Using linear programming, we find the extremal graphs or give good bounds for this index when the number n_k of vertices of degree kis n?k+t, for 0tk and kn/2. We also prove that for n_kn?k, (kn/2) the minimum value of the Randi? index is attained for the graph .     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers k_u and k_l, decide whether there is a minimum vertex cover in G with at most k_u vertices in U and at most k_l vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26^k_u+k_l+(k_u+k_l)|G|) and significantly improves previous algorithms for the problem.     

On the adjacent vertex distinguishing edge colourings of graphs

A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ′_a(G), is the minimum number of colours needed in an avd-colouring of G. It is proved that for any connected 3-colourable Hamiltonian graph G, we have χ′_a(G)≤Δ+3.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

Inverse degree and super edge-connectivity

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ _v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n?2δ)/(n?δ) (n?δ?1), then G is super edge-connected. We also give an analogous result for triangle-free graphs.     

On the pseudoachromatic number of join of graphs

Given an undirected graph G = (V, E), with vertex set V and edge set E, the pseudoachromatic number ψ(G) of the graph G is the maximum number of colors used to color the vertices in such a way that, for any given pair of colors i, j there exists an edge e = (u, v) ∈ E(G) such that u is colored i and v is colored j. In this paper we give a complete characterization of when the ψ of the join of any two graphs is the sum of the ψ of the two graphs.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

General-demand disjoint path covers in a graph with faulty elements

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.     

Vertex arboricity of planar graphs without chordal 6-cycles

The vertex arboricity va(G) of a graph G is the minimum number of colours the vertices can be coloured so that each colour class induces a forest. It was known that va(G)≤3 for every planar graph G, and the problem of computing vertex arboricity of graphs is NP-hard. In this paper, we prove that va(G)≤2 if G is a planar graph without chordal 6-cycles. This extends a result by Raspaud and Wang [On the vertex-arboricity of planar graphs, Eur. J. Combin. 29 (2008), pp. 1064–1075].