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 6 Next

Displaying 101 – 120 of 390

Showing per page

Chvátal-Erdos condition and pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Ingo Schiermeyer, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.

Chvátal-Erdös type theorems

Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant (2010)

Discussiones Mathematicae Graph Theory

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that d i > i or d n - i ≥ n - i . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Ciclos de Hamilton en redes de paso conmutativo y de paso fijo.

Miguel Angel Fiol Mora, José Luis Andrés Yebra (1988)

Stochastica

From a natural generalization to Z2 of the concept of congruence, it is possible to define a family of 2-regular digraphs that we call commutative-step networks. Particular examples of such digraphs are the cartesian product of two directed cycles, C1 x Ch, and the fixed-step network (or 2-step circulant digraph) DN,a,b.In this paper the theory of congruences in Z2 is applied to derive three equivalent characterizations of those commutative-step networks that have a Hamiltonian cycle. Some known...

Circuit bases of strongly connected digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler (2003)

Discussiones Mathematicae Graph Theory

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.

Circular distance in directed graphs

Bohdan Zelinka (1997)

Mathematica Bohemica

Circular distance d ∘ ( x , y ) between two vertices x , y of a strongly connected directed graph G is the sum d ( x , y ) + d ( y , x ) , where d is the usual distance in digraphs. Its basic properties are studied.

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph ℋ d ̲ , d ̅ ( S ) = ( V , ) where V = S and = e ⊆ S : d ̲ < | e | < d ̅ ∧ ∑ v ∈ e v ∈ S . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices w ₁ , . . . , w σ ∉ V such that ℋ ∪ w ₁ , . . . , w σ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities...

Classification of rings with toroidal Jacobson graph

Krishnan Selvakumar, Manoharan Subajini (2016)

Czechoslovak Mathematical Journal

Let R be a commutative ring with nonzero identity and J ( R ) the Jacobson radical of R . The Jacobson graph of R , denoted by 𝔍 R , is defined as the graph with vertex set R ∖ J ( R ) such that two distinct vertices x and y are adjacent if and only if 1 - x y is not a unit of R . The genus of a simple graph G is the smallest nonnegative integer n such that G can be embedded into an orientable surface S n . In this paper, we investigate the genus number of the compact Riemann surface in which 𝔍 R can be embedded and explicitly...

Currently displaying 101 – 120 of 390