On distances in some bipartite graphs.
On equality of edge-connectivity and minimum degree of a graph
On eulerian irregularity in graphs
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 extremal graphs with no long paths.
On functions which sum to zero on semicycles
On graphs with nonisomorphic -neighbourhoods
On -closed graphs
On Hamilton Circuits and Hamilton Paths.
On hereditary properties of composition graphs
The composition graph of a family of n+1 disjoint graphs 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 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 identifying codes in the King grid that are robust against edge deletions.
On independent sets and non-augmentable paths in directed graphs
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 -domatic numbers of graphs
On k-closure operators in graphs
On kernels by monochromatic paths in the corona of digraphs
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
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...
On lengths of rainbow cycles.
On long cycles through four prescribed vertices of a polyhedral graph
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
On longest circuits in certain non-regular planar graphs
On Longest Cycles in Essentially 4-Connected Planar Graphs
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...
On monochromatic paths and bicolored subdigraphs in arc-colored tournaments
Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...