Displaying 141 – 160 of 1226

Showing per page

A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez, Sergio Rajsbaum (1998)

Discussiones Mathematicae Graph Theory

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote I γ ( C ) = | A ( γ ) A ( C ) | , the number of arcs that γ and Cₖ have in common. Let f ( k , T , γ ) = m a x I γ ( C ) | C T and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...

A conjecture on the prevalence of cubic bridge graphs

Jerzy A. Filar, Michael Haythorpe, Giang T. Nguyen (2010)

Discussiones Mathematicae Graph Theory

Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Dávid Mesežnikov (2012)

Kybernetika

For any d 11 we construct graphs of degree d , diameter 2 , and order 8 25 d 2 + O ( d ) , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of 9 25 d 2 + O ( d ) has been known [3] but it applies only to special values of degrees d depending on prime powers.

A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs

Ji-Yun Guo, Jian-Hua Yin (2017)

Discussiones Mathematicae Graph Theory

Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for...

A De Bruijn-Erdős theorem for 1 - 2 metric spaces

Václav Chvátal (2014)

Czechoslovak Mathematical Journal

A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvátal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces where each nonzero distance equals 1 or 2 .

A deceptive fact about functions

Wiesław Dziobiak, Andrzej Ehrenfeucht, Jacqueline Grace, Donald Silberger (2000)

Fundamenta Mathematicae

The paper provides a proof of a combinatorial result which pertains to the characterization of the set of equations which are solvable in the composition monoid of all partial functions on an infinite set.

Currently displaying 141 – 160 of 1226