The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there...

For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic...

If $G$ is a connected graph of order $n\ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in V\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);z\in V\left(G\right)\left)\right),$$ where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n\ge 3$. Assume that there exists a subgraph...

An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)|...

By a ternary structure we mean an ordered pair $(X_0,T_0)$, where $X_0$ is a finite nonempty set and $T_0$ is a ternary relation on $X_0$. By the underlying graph of a ternary structure $(X_0,T_0)$ we mean the (undirected) graph $G$ with the properties that $X_0$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if $$\{x\in X_0{T}_0(u,x,v)\}\cup \{x\in X_0{T}_0(v,x,u)\}=\{u,v\}.$$ A ternary structure $(X_0,T_0)$ is said to be the B-structure of a connected graph $G$ if $X_0$ is the vertex set of $G$ and the following statement holds for all $u,x,y\in X_0$: $T_0(x,u,y)$ if and only if $u$ belongs to an induced $x-y$...

Let G be a graph with n vertices and ν(G) be the matching number of G. The inertia of a graph G, In(G) = (n₊,n₋,n₀) is an integer triple specifying the numbers of positive, negative and zero eigenvalues of the adjacency matrix A(G), respectively. Let η(G) = n₀ denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G) = n - 2ν(G). Guo et al. [Ji-Ming Guo, Weigen Yan and Yeong-Nan Yeh. On the nullity and the matching number of unicyclic...

In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .

Bondy and Erdős [2] have conjectured that the Ramsey number for three cycles Cₖ of odd length has value r(Cₖ,Cₖ,Cₖ) = 4k-3. We give a proof that r(C₇,C₇,C₇) = 25 without using any computer support.

A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter mp(G). We call G saturated if, for every edge e added to G, mp(G + e) > mp(G),...

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with $n$ vertices and $k$ pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with $n$ vertices and $k$ pendant vertices, respectively....

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k\left(G\right)$ contains a 2-factor.

We give the Turán number ex (n, 2P5) for all positive integers n, improving one of the results of Bushaw and Kettle [Turán numbers of multiple paths and equibipartite forests, Combininatorics, Probability and Computing, 20 (2011) 837-853]. In particular we prove that ex (n, 2P5) = 3n−5 for n ≥ 18.