Route systems of a connected graph
The concept of a route system was introduced by the present author in [3].Route systems of a connected graph generalize the set of all shortest paths in . In this paper some properties of route systems are studied.
Route systems on graphs
The well known types of routes in graphs and directed graphs, such as walks, trails, paths, and induced paths, are characterized using axioms on vertex sequences. Thus non-graphic characterizations of the various types of routes are obtained.
Self-dual non-Hamiltonian polyhedra with only two types of faces
Several results on chordal bipartite graphs
The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that,...
Short cycles in digraphs with local average outdegree at least two.
Short cycles in random regular graphs.
Short cycles of low weight in normal plane maps with minimum degree 5
In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with . These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.
Short paths in 3-uniform quasi-random hypergraphs
Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms...
Shortness coefficient of cyclically 5-connected cubic planar graphs.
Shortness coefficient of cyclically 5-connected cubic planar graphs. (Short Communication).
Signpost systems and spanning trees of graphs
By a ternary system we mean an ordered pair , where is a finite nonempty set and . By a signpost system we mean a ternary system satisfying the following conditions for all : if , then and ; if , then there exists such that . In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair , where is a connected graph and is a spanning tree of . If is a ct-pair, then by the guide to...
Simple 3-polytopal graphs with edges of only two types and shortness coefficients
Skolem-type difference sets for cycle systems.
Some applications of the proper and adjacency polynomials in the theory of graph spectra.
Some crossing numbers of products of cycles
The exact values of crossing numbers of the Cartesian products of four special graphs of order five with cycles are given and, in addition, all known crossing numbers of Cartesian products of cycles with connected graphs on five vertices are summarized.
Some graphic uses of an even number of odd nodes
Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.
Some gregarious cycle decompositions of complete equipartite graphs.
Some hardness results for question/answer games.
Spanning trees of bounded degree.
Spanning trees of locally finite graphs