On a generalization of Meyniel's conjecture on the Cops and Robbers game.
On a generalization of perfect -matching
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On a generalization of the friendship theorem
The Friendship Theorem states that if any two people, of a group of at least three people, have exactly one friend in common, then there is always a person who is everybody's friend. In this paper, we generalize the Friendship Theorem to the case that in a group of at least three people, if every two friends have one or two common friends and every pair of strangers have exactly one friend then there exist one person who is friend to everybody in the group. In particular, we show that the graph...
On a generalization of the matroid
On a graph invariant related to the sum of all distances in a graph.
On a graph theory problem of M. Koman
On a Graph Transformation That Preserves the Stability Number
On a Hamiltonian cycle of the fourth power of a connected graph
In this paper the following theorem is proved: Let be a connected graph of order and let be a matching in . Then there exists a hamiltonian cycle of such that .
On a local property of the unoriented graph of a modular multilattice
On a matching distance between rooted phylogenetic trees
The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values...
On a maximal distance between graphs
On a minimum cycle basis of a graph
On a pair of functional equations of combinatorial interest.
On a perfect problem
We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that (a) C does not include all perfect graphs and (b) every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C? A class P is called...
On a power of cyclically ordered sets
On a problem concerning -subdomination numbers of graphs
One of numerical invariants concerning domination in graphs is the -subdomination number of a graph . A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph with vertices and any with the inequality holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and .
On a problem concerning stratified graphs
On a Problem in Map Colouring
On a problem of colouring the real plane
What is the least number of colours which can be used to colour all points of the real Euclidean plane so that no two points which are unit distance apart have the same colour? This well known problem, open more than 25 years is studied in the paper. Some partial results and open subproblems are presented.
On a problem of Davison. (Summary).