The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 121 –
140 of
513
In this note, we consider the problem of existence of an edge-decomposition of a multigraph into isomorphic copies of 2-edge paths . We find necessary and sufficient conditions for such a decomposition of a multigraph H to exist when
(i) either H does not have incident multiple edges or
(ii) multiplicities of the edges in H are not greater than two. In particular, we answer a problem stated by Z. Skupień.
It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each n ≥ 3. The...
For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.
In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c).
The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G = Cₘ × Kₙ, c)...
Let , and be a non-increasing sequence of nonnegative integers. If has a realization with vertex set such that for and is a cycle of length in , then is said to be potentially -graphic. In this paper, we give a characterization for to be potentially -graphic.
The line graph of a graph , denoted by , has as its vertex set, where two vertices in are adjacent if and only if the corresponding edges in have a vertex in common. For a graph , define . Let be a 2-connected claw-free simple graph of order with . We show that, if and is sufficiently large, then either is traceable or the Ryjáček’s closure , where is an essentially -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10 which have...
A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 edges is AP or belongs to few classes of exceptional graphs.
The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.
2010 Mathematics Subject Classification: 05C38, 05C45.In 1952, Dirac introduced the degree type condition and proved that if G is a connected graph of order n і 3 such that its minimum degree satisfies d(G) і n/2, then G is Hamiltonian. In this paper we investigate a further condition and prove that if G is a connected graph of order n і 3 such that d(G) і (n-2)/2, then G is Hamiltonian or G belongs to four classes of well-structured exceptional graphs.
We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.
For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number is the maximum cardinality of a D-independent set. In particular, the independence number . Along with general results we consider, in particular, the odd-independence number where ODD = 1,3,5,....
Currently displaying 121 –
140 of
513