BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(G), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex Kr+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.
An odd [1,b]-factor of a graph G is a spanning subgraph H such that for each vertex v∈V(G), dH(v) is odd and 1≤dH(v)≤b. Let λ3(G) be the third largest eigenvalue of the adjacency matrix of G. For positive integers r≥3 and even n, Lu, Wu, and Yang [10] proved a lower bound for λ3(G) in an n-vertex r-regular graph G to gurantee the existence of an odd [1,b]-factor in G. In this paper, we improve the bound; it is sharp for every r.
The k-independence number of a graph G is the maximum size of a set of vertices at pairwise distance greater than k. In this paper, for each positive integer k, we prove sharp upper bounds for the k-independence number in an n-vertex connected graph with given minimum and maximum degree.
A {\it fractional matching} of a graph G is a function f giving each edge a number in [0,1] so that ∑e∈Γ(v)f(e)≤1 for each v∈V(G), where Γ(v) is the set of edges incident to v. The {\it fractional matching number} of G, written α∗′(G), is the maximum of ∑e∈E(G)f(e) over all fractional matchings f. Let G be an n-vertex connected graph with minimum degree d, let λ1(G) be the largest eigenvalue of G, and let k be a positive integer less than n. In this paper, we prove that if λ1(G)<d1+n−k2k, then α∗′(G)>2n−k. As a result, we prove α∗′(G)≥λ1(G)2+d2nd2, we characterize when equality holds in the bound.
Let G be a d-regular multigraph, and let λ2(G) be the second largest eigenvalue of G. In this paper, we prove that if λ2(G)<4d−1+9d2−10d+17, then G is 2-edge-connected. Furthermore, for t≥2 we show that G is (t+1)-edge-connected when λ2(G)<d−t, and in fact when λ2(G)<d−t+1 if t is odd.
In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.