All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 71

Showing per page

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

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

Endre Boros, Robert E. Jamison, Renu Laskar, Henry Martyn Mulder (2004)

Discussiones Mathematicae Graph Theory

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 generalization of the friendship theorem

Mohammad Hailat (2012)

Discussiones Mathematicae Graph Theory

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

Elena Wisztová (1991)

Mathematica Bohemica

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 distance local connectivity and vertex distance colouring

Přemysl Holub (2007)

Discussiones Mathematicae Graph Theory

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 dually compact closed classes of graphs and BFS-constructible graphs

Norbert Polat (2003)

Discussiones Mathematicae Graph Theory

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 generating sets of induced-hereditary properties

Gabriel Semanišin (2002)

Discussiones Mathematicae Graph Theory

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

Yahya Talebi, Atefeh Darzi (2017)

Commentationes Mathematicae Universitatis Carolinae

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

Shinya Fujita (2005)

Discussiones Mathematicae Graph Theory

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.

Currently displaying 1 – 20 of 71

Page 1 Next