Pentavalent symmetric graphs of order 16p

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, a complete classification of connected pentavalent symmetric graphs of order 16p is given for each prime p. It follows from this result that a connected pentavalent symmetric graph of order 16p exists if and only if p = 2 or 31, and that up to isomorphism, there are three such graphs.     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

Connected graphs with a minimal number of spanning trees

The problem studied is the following: Find a simple connected graph G with given numbers of vertices and edges which minimizes the number t_μ(G), the number of spanning trees of the multigraph obtained from G by adding μ parallel edges between every pair of distinct vertices. If G is nearly complete (the number of edges qis ≥(₂^P)?p+2 where p is the number of vertices), then the solution to the minimization problem is unique (up to isomorphism) and the same for all values of μ. The present paper investigates the case whereq<(₂^P)?p+2. In this case the solution is not always unique and there does not always exist a common solution for all values of μ. A (small) class of graphs is given such that for any μ there exists a solution to the problem which is contained in this class. For μ = 0 there is only one graph in the class which solves the problem. This graph is described and the minimum value of t₀(G) is found. In order to derive these results a representation theorem is proved for the cofactors of a special class of matrices which contains the tree matrices associated with graphs.     

An optimal parallel connectivity algorithm

A synchronized parallel algorithm of depth O(n²/p) for p (≤n²/log²n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.     

On disconnected cuts and separators

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V?U)∪{u} is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Plane Graphs with Parity Constraints

Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point ${p\in S}$ if the parity of the degree of p in G matches its label. In this paper, we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation that satisfy all but at most three parity constraints. For triangulations we can satisfy about 2/3 of the parity constraints and we show that in the worst case there is a linear number of constraints that cannot be fulfilled. In addition, we prove that for a given simple polygon H with polygonal holes on S, it is NP-complete to decide whether there exists a triangulation of H that satisfies all parity constraints.     

Maximum information stored in a labeled connected network with minimum edges

Given a set X, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1, . . . , m, the subgraph G _i induced from pattern i is a label connected graph with minimum edges. In the paper, we show that the problem is NP hard and develop a heuristic algorithm to get a fewer number of edges to store patterns.     

Edge decompositions into two kinds of graphs

Let H be an arbitrary graph and let K_1,2 be the 2-edge star. By a {K_1,2,H}-decomposition of a graph G we mean a partition of the edge set of G into subsets inducing subgraphs isomorphic to K_1,2 or H. Let J be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph G has a {K_1,2,H}-decomposition is NP-complete if H has a component of an odd size and H≠pK_1,2∪qJ, where pK_1,2∪qJ is the disjoint union of p copies of K_1,2 and q copies of J. Moreover, we prove polynomiality of this problem for H=qJ.     

The Critical Group of a Line Graph

The critical group of a graph is a finite abelian group whose order is the number of spanning forests of the graph. This paper provides three basic structural results on the critical group of a line graph.

• The first deals with connected graphs containing no cut-edge. Here the number of independent cycles in the graph, which is known to bound the number of generators for the critical group of the graph, is shown also to bound the number of generators for the critical group of its line graph.

• The second gives, for each prime p, a constraint on the p-primary structure of the critical group, based on the largest power of p dividing all sums of degrees of two adjacent vertices.

• The third deals with connected graphs whose line graph is regular. Here known results relating the number of spanning trees of the graph and of its line graph are sharpened to exact sequences which relate their critical groups.

The first two results interact extremely well with the third. For example, they imply that in a regular nonbipartite graph, the critical group of the graph and that of its line graph determine each other uniquely in a simple fashion.     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

Existence of graphs with a given set of r-neighborhoods

The problem of whether there exists a graph satisfying a particular set of local constraints can often be reduced to questions of the following sort: given a finite collection Φ of graphs, is there a graph G such that the set of r-neighborhoods of the vertices of G is precisely Φ? It is shown that, although such a question is in general recursively unsolvable, it becomes solvable when a bound on cycle length is imposed on G, even when G is required to be connected or arbitrarily large. This result is used to demonstrate the solvability of a problem from hypergraph theory involving degree sets of k-trees.     

Edge-transitive dihedral or cyclic covers of cubic symmetric graphs of order 2P

A regular cover of a connected graph is called dihedral or cyclic if its transformation group is dihedral or cyclic, respectively. Let X be a connected cubic symmetric graph of order 2p for a prime p. Several publications have investigated the classification of edge-transitive dihedral or cyclic covers of X for specific p. The edge-transitive dihedral covers of X have been classified for p=2 and the edge-transitive cyclic covers of X have been classified for p≤5. In this paper an extension of the above results to an arbitrary prime p is presented.     

Diameter-sufficient conditions for a graph to be super-restricted connected

A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex u in G has all its neighbors in X. Clearly, each connected component of G−X must have at least two vertices. The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a restricted cut. Additionally, if the deletion of a minimum restricted cut isolates one edge, then the graph is said to be super-restricted connected. In this paper, several sufficient conditions yielding super-restricted-connected graphs are given in terms of the girth and the diameter. The corresponding problem for super-edge-restricted-connected graph is also studied.     

Optimal stopping in a search for a vertex with full degree in a random graph

We consider the following on-line decision problem. The vertices of a realization of the random graph G(n,p) are being observed one by one by a selector. At time m, the selector examines the mth vertex and knows the graph induced by the m vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that this vertex has full degree, i.e. it is connected to all other vertices in the graph. An optimal algorithm for such a choice (in other words, optimal stopping time) is given. We show that it is of a threshold type and we find the threshold and its asymptotic estimation.     

Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

On the complexity of recognizing directed path families

A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G such that each word in the language is the set of arcs of some path in G, is a polynomial-time solvable problem.