On the complexity of the k-customer vehicle routing problem

We investigate the complexity of the k-CUSTOMER VEHICLE ROUTING PROBLEM: Given an edge weighted graph, the problem requires to compute a minimum weight set of cyclic routes such that each contains a distinguished depot vertex and at most other k customer vertices, and every customer belongs to exactly one route.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

Heavy cycles in k-connected weighted graphs with large weighted degree sums

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.     

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.     

On low degree k-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian) if, for any sequence of k distinct vertices v₁,…,v_k of G, there exists a cycle (respectively, a hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability, and motivated by the fact that k-orderedness of a graph implies (k-1)-connectivity, they posed the question of the existence of low degree k-ordered hamiltonian graphs. We construct an infinite family of graphs, which we call bracelet graphs, that are (k-1)-regular and are k-ordered hamiltonian for odd k. This result provides the best possible answer to the question of the existence of low degree k-ordered hamiltonian graphs for odd k. We further show that for even k, there exist no k-ordered bracelet graphs with minimum degree k-1 and maximum degree less than k+2, and we exhibit an infinite family of bracelet graphs with minimum degree k-1 and maximum degree k+2 that are k-ordered for even k. A concept related to k-orderedness, namely that of k-edge-orderedness, is likewise strongly related to connectivity properties. We study this relation and give bounds on the connectivity necessary to imply k-(edge-)orderedness properties.     

On the k-index of graphs

Given a graph, join every two vertices which are at a distance greater than a fixed integer k (>1)by a new path of length k. Thus a graph transformation is defined. The least number of iterations of this transformation such that the last iteration does not change the graph, is called the k-index of the original graph. In the present paper the graphs are classified according to their k-indices. The results are applied in the study of so-called tied graphs.     

Subclasses of k-trees: Characterization and recognition

A k-tree is either a complete graph on k vertices or a graph G=(V,E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees.     

On solving the planar k-centrum problem with Euclidean distances

This paper presents a solution procedure based on a gradient descent method for the k-centrum problem in the plane. The particular framework of this problem for the Euclidean norm leads to bisector lines whose analytical expressions are easy to handle. This allows us to develop different solution procedures which are tested on different problems and compared with existing procedures in the literature of Location Analysis. The computational analysis reports that our procedures provide better results than the existing ones for the k-centrum problem.     

Steiner centers in graphs

The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n-eccentricity e_n(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n-diameter of G is the maximum n-eccentricity among the vertices of G while the n-radius of G is the minimum n-eccentricity. The n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. It is shown that every graph is the n-center of some graph. Several results on the n-center of a tree are established. In particular, it is shown that the n-center of a tree is a tree and those trees that are n-centers of trees are characterized.     

Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

Based on an application in forestry, we study the dense k  -subgraph problem: Given a parameter k∈N$k\in \mathbb{N}$ and an undirected weighted graph G, the task is to find a subgraph of G with k vertices such that the sum of the weights of the induced edges is maximized. The problem is well-known to be NP-hard and difficult to approximate if the underlying graph does not satisfy the triangle inequality.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

Essential elements in connected k-polymatroids

It is a well-known result of Tutte that, for every element x of a connected matroid M, at least one of the deletion and contraction of x from M is connected. This paper shows that, in a connected k-polymatroid, only two such elements are guaranteed. We show that this bound is sharp and characterize those 2-polymatroids that achieve this minimum. To this end, we define and make use of a generalized parallel connection for k-polymatroids that allows connecting across elements of different ranks. This study of essential elements gives results crucial to finding the unavoidable minors of connected 2-polymatroids, which will appear elsewhere.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

Review of recent results about theκ-centrum of a tree

This paper is concerned with the-centrum of a graph. This concept, related to a particular location problem, generalizes that of the center and that of the median of a graph: the-centrum is the set of points for which the sum of the (weighted) distances from the farthest vertices is minimized. The paper will review some recent results about this problem. In particular, some properties of cardinality, connectivity and, more generally, of the structure of the-centrum of a weighted tree will be presented.     

Separating subgraphs in k-trees: Cables and caterpillars

The class of k-trees has the property that the minimal sets of vertices separating two nonadjacent vertices u and v of a k-tree Q induce k-complete subgraphs. We show that the union T of these subgraphs belongs to a subclass of (k ? 1)-trees which generalizes caterpillars. The maximum order of a monochromatic set of vertices in the optimal coloring of this (k ? 1)-tree T determines the length of the minimal collection of k vertex-disjoint paths between the two vertices of Q, the u, v-cable, which is spanned on all vertices of T.     

A constructive characterization of trees with at least k disjoint maximum matchings

Let H = F(v) ⊕ G(w) denote the graph obtained from F and G by identifying vertices v of F and w of G; H will be said to be obtained by surgery on F and G. A matching of a graph is a collection of edges, no two of which are incident with the same vertex. This paper presents a constructive characterization of the set S_k (k ≥ 2) of trees which have at least k disjoint maximum matchings. There are three types of surgery such that, for each k ≥ 2, S_k is the set of all trees obtainable from a star K_1.n (n ≥ k) by a finite sequence of the specified surgical operations. A constructive characterization is also given for trees with two disjoint maximum indepent vertex sets.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

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.     

A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph

The notion of a competition graph was introduced by Cohen in 1968. The competition graph C(D) of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.     

Characterization of k-variegated graphs, k ⩾ 3

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. Bednarek and Sanders [1] posed the problem of characterizing k-variegated graphs. V.N. Bhat-Nayak, S.A. Choudum and R.N. Naik [2] gave the characterization of 2-variegated graphs. In this paper we characterize k-variegated graphs for k ? 3.