Vertex-Disjoint Cycles of Order Eight with Chords in a Bipartite Graph

January 2013
Asian Academy of Management Journal of Accounting & Finance;2013, Vol. 9 Issue 1, p255
Academic Journal
Let G = (V1,V1;E) be a bipartite graph with ∣V1∣=∣V2∣= 4k, where k is a positive integer. In this paper, it is proved that if the minimum degree of G is at least 3k+1, then G contains k vertex-disjoint cycles of order eight such that each of them has at least two chords.


Related Articles

  • ...-Factorization of Complete Bipartite Symmetric Digraphs. Rajput, U. S.; Shukla, Bal Govind // International Journal of Computer Applications;Jul2013, Vol. 73 Issue 1-22, p40 

    In path factorization, H.Wang [1] gives the necessary and sufficient conditions for the existence of Pk-factorization of a complete bipartite graph for k, an even integer. Further, Beiling Du [2] extended the work of H. Wang, and studied the P2k-factorization of complete bipartite multigraph....

  • THE LIST LINEAR ARBORICITY OF PLANAR GRAPHS. Xinhui An; Baoyindureng Wu // Discussiones Mathematicae: Graph Theory;2009, Vol. 29 Issue 3, p499 

    The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar...

  • POTENTIALLY H-BIGRAPHIC SEQUENCES. Ferrara, Michael; Jacobson, Michael; Schmitt, John; Siggers, Mark // Discussiones Mathematicae: Graph Theory;2009, Vol. 29 Issue 3, p583 

    We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A, B) is said to be bigraphic if there is some bipartite graph G = (X ?Y, E) such that A and B are the degrees of the vertices in X and Y, respectively. If S...

  • Bipartite Powers of k-chordal Graphs. Chandran, L. Sunil; Mathew, Rogers // Discrete Mathematics & Theoretical Computer Science (DMTCS);2013, Vol. 15 Issue 2, p49 

    Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is...

  • POWER OF GRAPH WITH (2, 2) -BIPARTITION. Prasad, K. Manjunatha; Sudhakara, G.; Soumya, K. V. // Advances & Applications in Discrete Mathematics;Jul2015, Vol. 16 Issue 1, p51 

    We characterize the structure of graph G and the integers k for which the kth power of the graph G, Gk is (2, 2) -bipartite, whenever the graph G is among cycle, n-cube and tree.

  • On the Biclique Cover of the Complete Graph. Moazami, Farokhlagha; Soltankhah, Nasrin // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2347 

    Let $$K$$ be a set of $$k$$ positive integers. A biclique cover of type $$K$$ of a graph $$G$$ is a collection of complete bipartite subgraphs of $$G$$ such that for every edge $$e$$ of $$G$$ , the number of bicliques need to cover $$e$$ is a member of $$K$$ . If $$K=\{1,2,\ldots , k\}$$ then...

  • Chordal Bipartite Graphs with High Boxicity. Chandran, L.; Francis, Mathew; Mathew, Rogers // Graphs & Combinatorics;May2011, Vol. 27 Issue 3, p353 

    The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki...

  • On the Basis Number of the Strong Product of Theta Graphs with Cycles. Jaradat, M. M. M.; Janem, M. F.; Alawneh, A. J. // International Journal of Mathematical Combinatorics;Oct2008, Vol. 3, p40 

    A basis B for the cycle space C(G) of a graph G is called a d-fold if each edge of G occurs in at most d of the cycles in the basis B. A basis B for the cycle space C(G) of a graph G is Smarandachely if each edge of G occurs in at least 2 of the cycles in B. The basis number, b(G), of a graph G...

  • P→9—Factorization of Symmetric Complete Bipartite Digraph. Rajput, U. S.; Shukla, Bal Govind // International Journal of Computer Applications;Mar2013, Vol. 66, p14 

    In path factorization, Ushio [1] gave the necessary and sufficient conditions for Pk-design when k is odd. P2p-factorization of a complete bipartite graph for p an integer, was studied by Wang [2]. Further, Beiling [3] extended the work of Wang [2], and studied P2k-factorization of complete...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics