### Heterochromatic matchings in edge-colored graphs.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

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

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}(u,v)$ being the distance of u and v on a hamiltonian cycle of G.

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

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

Let $G=\left(V\right(G),E(G\left)\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[\{y\in V\left(G\right)\phantom{\rule{0.277778em}{0ex}}1\le {\mathrm{dist}}_{G}(x,y)\le 2\}\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**