A graph is -saturated if it contains no as a subgraph, but does contain after the addition of any edge in the complement of . The saturation number, , is the minimum number of edges of a graph in the set of all -saturated graphs of order . We determine the saturation number for and characterize the extremal graphs for .
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,...
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.
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...
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...
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.
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.