Displaying 261 – 280 of 908

Showing per page

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 K 1 , t -free, then minΔ(G),Δ(G̅) ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.

On graphs with a unique minimum hull set

Gary Chartrand, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link L ( v i ) = G i for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.

On Graphs with Disjoint Dominating and 2-Dominating Sets

Michael A. Henning, Douglas F. Rall (2013)

Discussiones Mathematicae Graph Theory

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the...

On graphs with maximum size in their switching classes

Sergiy Kozerenko (2015)

Commentationes Mathematicae Universitatis Carolinae

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...

On graphs with the largest Laplacian index

Bo Lian Liu, Zhibo Chen, Muhuo Liu (2008)

Czechoslovak Mathematical Journal

Let G be a connected simple graph on n vertices. The Laplacian index of G , namely, the greatest Laplacian eigenvalue of G , is well known to be bounded above by n . In this paper, we give structural characterizations for graphs G with the largest Laplacian index n . Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on n and k for the existence of a k -regular graph G of order n with the largest Laplacian...

Currently displaying 261 – 280 of 908