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.
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...
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...
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 .
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.
In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization of triangle-free...
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...
In this Note, we study infinite graphs with locally finite outerplane embeddings, given a characterization by forbidden subgraphs.
A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition V₁, V₂, ..., Vₙ of V(G) such that for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class of all (₁,₂,...,ₙ)-partitionable...
The concept of the -pairable graphs was introduced by Zhibo Chen (On -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter , called the pair length of a graph , as the maximum such that is -pairable and if is not -pairable for any positive integer . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars and and a light 4-path P₄. The results obtained for and P₄ are best possible.