All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 22 Next

Displaying 421 – 440 of 513

Showing per page

Route systems of a connected graph

Ladislav Nebeský (1994)

Mathematica Bohemica

The concept of a route system was introduced by the present author in [3].Route systems of a connected graph G generalize the set of all shortest paths in G . In this paper some properties of route systems are studied.

Route systems on graphs

Manoj Changat, Henry Martyn Mulder (2001)

Mathematica Bohemica

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.

Saturation numbers for linear forests P 6 + t P 2

Jingru Yan (2023)

Czechoslovak Mathematical Journal

A graph G is H -saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G . The saturation number, sat ( n , H ) , is the minimum number of edges of a graph in the set of all H -saturated graphs of order n . We determine the saturation number sat ( n , P 6 + t P 2 ) for n ≥ 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

Several results on chordal bipartite graphs

Mihály Bakonyi, Aaron Bono (1997)

Czechoslovak Mathematical Journal

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 of low weight in normal plane maps with minimum degree 5

Oleg V. Borodin, Douglas R. Woodall (1998)

Discussiones Mathematicae Graph Theory

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 w ( K 1 , 4 ) ≤ 30 . 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

Joanna Polcyn (2004)

Discussiones Mathematicae Graph Theory

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...

Signpost systems and spanning trees of graphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

By a ternary system we mean an ordered pair ( W , R ) , where W is a finite nonempty set and R ⊆ W × W × W . By a signpost system we mean a ternary system ( W , R ) satisfying the following conditions for all x , y , z ∈ W : if ( x , y , z ) ∈ R , then ( y , x , x ) ∈ R and ( y , x , z ) ∉ R ; if x ≠ y , then there exists t ∈ W such that ( x , t , y ) ∈ R . 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 ( G , T ) , where G is a connected graph and T is a spanning tree of G . If ( G , T ) is a ct-pair, then by the guide to...

Some crossing numbers of products of cycles

Marián Klešč (2005)

Discussiones Mathematicae Graph Theory

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

Kathie Cameron, Jack Edmonds (1999)

Annales de l'institut Fourier

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.

Currently displaying 421 – 440 of 513