Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

Heterochromatic matchings in edge-colored graphs.

The Electronic Journal of Combinatorics [electronic only]

Rainbow $H$-factors of complete $s$-uniform $r$-partite hypergraphs.

The Electronic Journal of Combinatorics [electronic only]

An Implicit Weighted Degree Condition For Heavy Cycles

Discussiones Mathematicae Graph Theory

For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains...

Pancyclism and small cycles in graphs

Discussiones Mathematicae Graph Theory

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), ${d}_{C}\left(u,v\right)$ being the distance of u and v on a hamiltonian cycle of G.

A note on a new condition implying pancyclism

Discussiones Mathematicae Graph Theory

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to ${K}_{n/2,n/2}$.

Chvátal-Erdos condition and pancyclism

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.

A Note on Neighbor Expanded Sum Distinguishing Index

Discussiones Mathematicae Graph Theory

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Two operations on a graph preserving the (non)existence of 2-factors in its line graph

Czechoslovak Mathematical Journal

Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a graph. Gould and Hynds (1999) showed a well-known characterization of $G$ by its line graph $L\left(G\right)$ that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph $G$ to have a 2-factor in its line graph $L\left(G\right).$ A graph $G$ is called ${N}^{2}$-locally connected if for every vertex $x\in V\left(G\right),$ $G\left[\left\{y\in V\left(G\right)\phantom{\rule{0.277778em}{0ex}}1\le {\mathrm{dist}}_{G}\left(x,y\right)\le 2\right\}\right]$ is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex...

Page 1