Some problems about linear arboricity

We present here a conjecture on partitioning the edges of a graph into k-linear forests (forest whose connected components are paths of length less or equal to k).     

On the uniform edge-partition of a tree

We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.     

High valency subgraphs of cubes

Let G be a subgraph of the 1-skeleton of the unit cube in R”, in which each vertex is of degree at least k. Our main result is that each connected component of G has at least 2^k vertices, and so G has at most 2^n?k components.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

Connector Families of Graphs

For every pair of fixed natural numbers k > l we consider families of subgraphs of the complete graph K _n such that each graph in the family has at least k connected components while the union of any two has at most l. We show that the cardinality of such a family is at most exponential in n and determine the exact exponential growth of the largest such families for every value of k and l = 1.     

A note on k-strongly connected orientations of an undirected graph

Each k-strongly connected orientation of an undirected graph can be obtained from any other k-strongly connected orientation by reserving consecutively directed paths or circuits without destroying the k-strongly connectivity.     

PTAS for the minimum k-path connected vertex cover problem in unit disk graphs

In the Minimum k-Path Connected Vertex Cover Problem (MkPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k ? 1 has a vertex in C, and moreover, the induced subgraph G[C] is connected. MkPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. MkPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for MkPCVCP in unit disk graphs, for every fixed k ≥ 2.     

On factorable degree sequences

We call a degree sequence graphic (respectively, k-factorable, connected k-factorable) if there exists a graph (respectively, a graph with a k-factor, a graph with a connected k-factor) with the given degree sequence. In this paper we give a necessary and sufficient condition for a k-factorable sequence to be connected k-factorable when k ? 2. We also prove that every k-factorable sequence is (k − 2) factorable and 2-factorable, and also 1-factorable, when the sequence is of even length. Some conjectures are stated and it is also proved that, if {d_i} and {d_i − k} are graphic, then {d_i − r} is graphic for 0 ≤ r ≤ k provided rn is even.     

Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size

At the 4th International Graph Theory Conference 1980, G. Chartrand posed the following problem: If a (connected) graph G contains spanning trees with m and n pendant vertices, respectively, with m < n, does G contain a spanning tree with k pendant vertices for every integer k, where m < k < n? Recently, S. Schuster showed that the answer is yes. Several variations of this interpolation theorem will be given including the following generalization: If a connected graph G contains connected spanning subgraphs of size r with m and n pendant vertices, respectively, with m < n, then G contains a connected spanning subgraph of size r with k pendant vertices for every integer k, where m < k < n.     

Edge fault tolerance analysis of super k-restricted connected networks

An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λ_k. In this paper, several sufficient conditions yielding super-λ_k graphs are given in terms of the girth and the diameter.