On the proof of a theorem of Pálfy.
On the pseudoachromatic number of a graph
On the quantum chromatic number of a graph.
On the rainbow connection of Cartesian products and their subgraphs
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed....
On the Rainbow Vertex-Connection
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5...
On the Ramsey-Turán number of finite graphs
On the recognition of bipolarizable and -simplicial graphs.
On the reconstruction of countable forests.
On the reconstruction of the matching polynomial and the reconstruction conjecture.
On the Relationships between Zero Forcing Numbers and Certain Graph Coverings
The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals...
On the resilience of long cycles in random graphs.
On the rooted Tutte polynomial
The Tutte polynomial is a generalization of the chromatic polynomial of graph colorings. Here we present an extension called the rooted Tutte polynomial, which is defined on a graph where one or more vertices are colored with prescribed colors. We establish a number of results pertaining to the rooted Tutte polynomial, including a duality relation in the case that all roots reside around a single face of a planar graph.
On the rules for the elimination of the non-canonical Morgan trees
On the second Laplacian spectral moment of a graph
Kragujevac (M. L. Kragujevac: On the Laplacian energy of a graph, Czech. Math. J. 56(131) (2006), 1207–1213) gave the definition of Laplacian energy of a graph and proved ; equality holds if and only if . In this paper we consider the relation between the Laplacian energy and the chromatic number of a graph and give an upper bound for the Laplacian energy on a connected graph.
On the second largest eigenvalue of a mixed graph
Let G be a mixed graph. We discuss the relation between the second largest eigenvalue λ₂(G) and the second largest degree d₂(G), and present a sufficient condition for λ₂(G) ≥ d₂(G).
On the selection of pairs
On the semigroup of fully indecomposable relations
On the set of all maximal matchings
On the set of all shortest paths of a given length in a connected graph
On the set of distances between two sets over finite fields.