TITLE

The Linear Arboricity of Planar Graphs without 5-Cycles with Chords

AUTHOR(S)
HONG-YU CHEN; XIANG TAN; JIAN-LIANG WU
PUB. DATE
July 2013
SOURCE
Asian Academy of Management Journal of Accounting & Finance;2013, Vol. 9 Issue 2, p285
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that for a planar graph G with maximum degree Δ (G) ≥ 7, la(G) = [(Δ(G))=2] if G has no 5-cycles with chords.
ACCESSION #
88053838

 

Related Articles

  • The Linear Arboricity of Planar Graphs with Maximum Degree at Least Five. XIANG TAN; HONGYU CHEN; JIANLIANG WU // Bulletin of the Malaysian Mathematical Sciences Society;2011, Vol. 34 Issue 3, p541 

    Let G be a planar graph with maximum degree Δ ≥ 5. It is proved that la(G) = ⌈Δ(G)/2⌉ if (1) any 4-cycle is not adjacent to an i-cycle for any i ϵ {3, 4, 5} or (2) G has no intersecting 4-cycles and intersecting i-cycles for some i ϵ {3, 6}.

  • Remarks on the Complexity of Non-negative Signed Domination. Chuan-Min Lee // Journal of Networks;Aug2014, Vol. 9 Issue 8, p2051 

    This paper is motivated by the concept of non-negative signed domination that was introduced by Huang, Li, and Feng in 2013 [15]. We study the non-negative signed domination problem from the theoretical point of view. For networks modeled by strongly chordal graphs and distance-hereditary...

  • Bipartite and Planar Power Graphs of Finite Groups. Maity, S. K. // Southeast Asian Bulletin of Mathematics;2015, Vol. 39 Issue 4, p539 

    The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a, b ∈ S are adjacent if and only if a ≠ b and am = b or bm = a for some positive integer m. In this paper we characterize the class of finite groups S for which G(S) is...

  • Necessary Condition for Cubic Planar 3-Connected Graph to be Non-Hamiltonian with Proof of Barnette's Conjecture. Shah, Mushtaq Ahmad // International Journal of Mathematical Combinatorics;Sep2014, Vol. 3, p70 

    A conjecture of Barnette states that, every three connected cubic bipartite planar graph is Hamiltonian. This problem has remained open since its formulation. This paper has a threefold purpose. The first is to provide survey of literature surrounding the conjecture. The second is to give the...

  • Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration. Eguía, Martiniano; Soulignac, Francisco J. // Discrete Mathematics & Theoretical Computer Science (DMTCS);2013, Vol. 15 Issue 1, p55 

    A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every...

  • Tenacity and Rupture Degree of Permutation Graphs of Complete Bipartite Graphs. FENGWEI LI; QINGFANG YE; XUELIANG LI // Bulletin of the Malaysian Mathematical Sciences Society;2011, Vol. 34 Issue 3, p423 

    Computer or communication networks are so designed that they do not easily get disrupted under external attack and, moreover, these are easily reconstructed when they do get disrupted. These desirable properties of networks can be measured by various parameters such as connectivity, toughness,...

  • A GOOD DRAWING OF COMPLETE BIPARTITE GRAPH K9;9, WHOSE CROSSING NUMBER HOLDS ZARANKIEWICZ CONJECTURES. FARAHANI, MOHAMMAD REZA // Studia Universitatis Babes-Bolyai, Informatica;Mar2013, Vol. 58 Issue 1, p21 

    There exist some Drawing for any graph G = (V;E) on plan. An important aim in Graph Theory and Computer science is obtained a best drawing of an arbitrary graph. Also, a draw of a non-planar graph G on plan generate several edge-cross. A good drawing (or strongly best drawing) of G is consist of...

  • An Upper Bound on the Number of Edges in an Almost Planar Bipartite Graph. Karpov, D. // Journal of Mathematical Sciences;Feb2014, Vol. 196 Issue 6, p737 

    Let G be a bipartite graph without loops and multiple edges on v ≥ 4 vertices, which can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that such a graph has at most 3 v - 8 edges for even v ≠ 6 and at most 3 v - 9 edges for odd v and...

  • The Cubical Matching Complex. Ehrenborg, Richard // Annals of Combinatorics;Mar2014, Vol. 18 Issue 1, p75 

    Given a bipartite planar graph embedded in the plane, we define its cubical matching complex. By combining results of Kalai and Propp, we show that the cubical matching complex is collapsible. As a corollary, we obtain that a simply connected region R in the plane that can be tiled with lozenges...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics