On some Ramsey and Turán-type numbers for paths and cycles.
On Systems of Paths and Circuits in Graphs.
On ternary square-free circular words.
On the acyclic point-connectivity of the n-cube.
On the basis number and the minimum cycle bases of the wreath product of some graphs i
A construction of a minimum cycle bases for the wreath product of some classes of graphs is presented. Moreover, the basis numbers for the wreath product of the same classes are determined.
On the basis number of the corona of graphs.
On the chromatic uniqueness of edge-gluing of complete tripartite graphs and cycles.
On the Cone of Nonnegative Circuits.
On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six
The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for all other...
On the crossing numbers of Cartesian products of stars and paths or cycles
On the Crossing Numbers of Cartesian Products of Wheels and Trees
Bokal developed an innovative method for finding the crossing numbers of Cartesian product of two arbitrarily large graphs. In this article, the crossing number of the join product of stars and cycles are given. Afterwards, using Bokal’s zip product operation, the crossing numbers of the Cartesian products of the wheel Wn and all trees T with maximum degree at most five are established.
On the distance polynomial of a graph
Several properties of the distance polynomial are discussed.
On the distance spectrum of a cycle
Analytic expressions for the roots of the distance polynomial of a cycle are given.
On the Domination of Cartesian Product of Directed Cycles: Results for Certain Equivalence Classes of Lengths
Let (−→ Cm2−→ Cn) be the domination number of the Cartesian product of directed cycles −→ Cm and −→ Cn for m, n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of (−→ Cm2−→ Cn) when m ≤ 6 and [12] when both m and n ≡ 0(mod 3). In this article we give, in general, the value of (−→ Cm2−→ Cn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].
On the Edge-Hyper-Hamiltonian Laceability of Balanced Hypercubes
The balanced hypercube BHn, defined by Wu and Huang, is a variant of the hypercube network Qn, and has been proved to have better properties than Qn with the same number of links and processors. For a bipartite graph G = (V0 ∪ V1,E), we say G is edge-hyper-Hamiltonian laceable if it is Hamiltonian laceable, and for any vertex v ∈ Vi, i ∈ {0, 1}, any edge e ∈ E(G − v), there is a Hamiltonian path containing e in G − v between any two vertices of V1−i. In this paper, we prove that BHn is edge-hy per-...
On the Erdős-Gyárfás Conjecture in Claw-Free Graphs
The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs
On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph
We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.
On the forcing geodetic and forcing steiner numbers of a graph
For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The...
On the Graph of Large Distances.
On the identification of vertices using cycles.