Old and new generalizations of line graphs.
On 2-periodic graphs of a certain graph operator
We deal with the graph operator defined to be the complement of the square of a graph: . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries...
On 3-simplicial vertices in planar graphs
A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.
On a certain homomorphism properties of graphs II.
On a characterization of graphs by average labellings
The additive hereditary property of linear forests is characterized by the existence of average labellings.
On a classification of Hamiltonian tournaments
On a conjecture concerning the Petersen graph.
On a facet of the balanced subgraph polytope
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 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 certain extensions of intervals in graphs
On cotree-critical and DFS cotree-critical graphs.
On distance local connectivity and vertex distance colouring
In this paper, we give some sufficient conditions for distance local connectivity of a graph, and a degree condition for local connectivity of a k-connected graph with large diameter. We study some relationships between t-distance chromatic number and distance local connectivity of a graph and give an upper bound on the t-distance chromatic number of a k-connected graph with diameter d.
On double covers of graphs
On dually compact closed classes of graphs and BFS-constructible graphs
A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite...
On extremal graphs with no long paths.
On generating sets of induced-hereditary properties
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization...
On graph associated to co-ideals of commutative semirings
Let be a commutative semiring with non-zero identity. In this paper, we introduce and study the graph whose vertices are all elements of and two distinct vertices and are adjacent if and only if the product of the co-ideals generated by and is . Also, we study the interplay between the graph-theoretic properties of this graph and some algebraic properties of semirings. Finally, we present some relationships between the zero-divisor graph and .
On graphs G for which both g and G̅ are claw-free
Let G be a graph with |V(G)| ≥ 10. We prove that if both G and G̅ are claw-free, then minΔ(G), Δ(G̅) ≤ 2. As a generalization of this result in the case where |V(G)| is sufficiently large, we also prove that if both G and G̅ are -free, then minΔ(G),Δ(G̅) ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.
On graphs with cyclic defect or excess.