Page 1 Next

Displaying 1 – 20 of 666

Showing per page

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such that v lies...

2-placement of (p,q)-trees

Beata Orchel (2003)

Discussiones Mathematicae Graph Theory

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which...

A bound on the k -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Let G be a graph with vertex set V ( G ) , and let k 1 be an integer. A subset D V ( G ) is called a k -dominating set if every vertex v V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) k + 1 , then we prove that γ k + 1 ( G ) | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...

A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez, Sergio Rajsbaum (1998)

Discussiones Mathematicae Graph Theory

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote I γ ( C ) = | A ( γ ) A ( C ) | , the number of arcs that γ and Cₖ have in common. Let f ( k , T , γ ) = m a x I γ ( C ) | C T and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...

A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Dávid Mesežnikov (2012)


For any d 11 we construct graphs of degree d , diameter 2 , and order 8 25 d 2 + O ( d ) , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of 9 25 d 2 + O ( d ) has been known [3] but it applies only to special values of degrees d depending on prime powers.

A Different Short Proof of Brooks’ Theorem

Landon Rabern (2014)

Discussiones Mathematicae Graph Theory

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

Currently displaying 1 – 20 of 666

Page 1 Next