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

Displaying 21 – 40 of 109

Showing per page

On constant-weight TSP-tours

Scott Jones, P. Mark Kayll, Bojan Mohar, Walter D. Wallis (2003)

Discussiones Mathematicae Graph Theory

Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant...

On degree sets and the minimum orders in bipartite graphs

Y. Manoussakis, H.P. Patil (2014)

Discussiones Mathematicae Graph Theory

For any simple graph G, let D(G) denote the degree set {degG(v) : v ∈ V (G)}. Let S be a finite, nonempty set of positive integers. In this paper, we first determine the families of graphs G which are unicyclic, bipartite satisfying D(G) = S, and further obtain the graphs of minimum orders in such families. More general, for a given pair (S, T) of finite, nonempty sets of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y ) such that D(X) = S, D(Y )...

On eulerian irregularity in graphs

Eric Andrews, Chira Lumduanhom, Ping Zhang (2014)

Discussiones Mathematicae Graph Theory

A closed walk in a connected graph G that contains every edge of G exactly once is an Eulerian circuit. A graph is Eulerian if it contains an Eulerian circuit. It is well known that a connected graph G is Eulerian if and only if every vertex of G is even. An Eulerian walk in a connected graph G is a closed walk that contains every edge of G at least once, while an irregular Eulerian walk in G is an Eulerian walk that encounters no two edges of G the same number of times. The minimum length of an...

On hereditary properties of composition graphs

Vadim E. Levit, Eugen Mandrescu (1998)

Discussiones Mathematicae Graph Theory

The composition graph of a family of n+1 disjoint graphs H i : 0 ≤ i ≤ n is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors H i : 0 ≤ i ≤ n have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the...

On independent sets and non-augmentable paths in directed graphs

H. Galeana-Sánchez (1998)

Discussiones Mathematicae Graph Theory

We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan...

On kernels by monochromatic paths in the corona of digraphs

Iwona Włoch (2008)

Open Mathematics

In this paper we derive necessary and sufficient conditions for the existence of kernels by monochromatic paths in the corona of digraphs. Using these results, we are able to prove the main result of this paper which provides necessary and sufficient conditions for the corona of digraphs to be monochromatic kernel-perfect. Moreover we calculate the total numbers of kernels by monochromatic paths, independent by monochromatic paths sets and dominating by monochromatic paths sets in this digraphs...

On k-Path Pancyclic Graphs

Zhenming Bi, Ping Zhang (2015)

Discussiones Mathematicae Graph Theory

For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G...

Currently displaying 21 – 40 of 109