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 k≥1 and n≥2k, the well known Kneser graph KG(n,k) has all k-element subsets of an n-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph SG(n,k) of KG(n,k) with the same chromatic number. In this paper, we compute the diameter of the graph SG(2k+r,k) with r≥1. We obtain an exact value of the diameter of SG(2k+r,k) when r∈{1,2} or when r≥k−3. For the remained cases, when 3≤r≤k−4, we obtain that the diameter of SG(2k+r,k) belongs to the integer interval [4..k−r−1].
Let G be a connected graph with V(G)={v1,…,vn}. The (i,j)-entry of the distance matrix D(G) of G is the distance between vi and vj. In this article, using the well-known Ramsey's theorem, we prove that for each integer k≥2, there is a finite amount of graphs whose distance matrices have rank k. We exhibit the list of graphs with distance matrices of rank 2 and 3. Besides, we study the rank of the distance matrices of graphs belonging to a family of graphs with their diameters at most two, the trivially perfect graphs. We show that for each η≥1 there exists a trivially perfect graph with nullity η. We also show that for threshold graphs, which are a subfamily of the family of trivially perfect graphs, the nullity is bounded by one.
In the present work we prove that given any two unicycle graphs (pseudoforests) that share the same degree sequence there is a finite sequence of 2-switches transforming one into the other such that all the graphs in the sequence are also unicyclic graphs (pseudoforests).
Given any two forests with the same degree sequence, we show in an algorithmic way that one can be transformed into the other by a sequence of 2-switches in such a way that all the intermediate graphs of the transformation are forests. We also prove that the 2-switch operation perturbs minimally some well-known integer parameters in families of graphs with the same degree sequence. Then, we apply these results to conclude that the studied parameters have the interval property on those families.
The family of all k-independent sets of a graph containing a fixed vertex v is called a {star} and v is called its center. Stars are interesting for their relation to Erdös-Ko-Rado graphs. Hurlbert and Kamat conjectured that in trees the largest stars are centered in leafs. This conjecture was disproven independently by Baber, Borg, and Feghali, Johnson, and Thomas. In this paper we introduce a tool to bound the size of stars centered at certain vertices by stars centered at leafs. We use this tool to show that caterpillars and sunlet graphs satisfy Hurlbert and Kamat's conjecture, and to show that the centers of the largest stars in lobsters are either leafs or spinal vertices of degree 2.
The Hamilton-Waterloo problem asks for which s and r the complete graph Kn can be decomposed into s copies of a given 2-factor F1 and r copies of a given 2-factor F2 (and one copy of a 1-factor if n is even). In this paper we generalize the problem to complete equipartite graphs K(n:m) and show that K(xyzw:m) can be decomposed into s copies of a 2-factor consisting of cycles of length xzm; and r copies of a 2-factor consisting of cycles of length yzm, whenever m is odd, s,r=1, gcd(x,z)=gcd(y,z)=1 and xyz=0(mod4). We also give some more general constructions where the cycles in a given two factor may have different lengths. We use these constructions to find solutions to the Hamilton-Waterloo problem for complete graphs.
The Hamilton-Waterloo Problem (HWP) in the case of Cm-factors and Cn-factors asks if Kv, where v is odd (or Kv−F, where F is a 1-factor and v is even), can be decomposed into r copies of a 2-factor made either entirely of m-cycles and s copies of a 2-factor made entirely of n-cycles. In this paper, we give some general constructions for such decompositions and apply them to the case where m=3 and n=3x. We settle the problem for odd v, except for a finite number of x values. When v is even, we make significant progress on the problem, although open cases are left. In particular, the difficult case of v even and s=1 is left open for many situations.
In this paper, we determine an explicit formula for the number of walks in Xn=Cay(Zn,Un), the unitary Cayley Graphs of order n, between any pair of its vertices. With this result, we give the number of representations of a fixed residue class modn as the sum of k units of Zn.
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.