Printer Friendly

SOME PROPERTIES OF GLUED GRAPHS AT COMPLETE CLONE IN THE VIEW OF ALGEBRAIC COMBINATORICS.

Byline: Seyyede Masoome Seyyedi and Farhad Rahmati

Abstract

A glued graph at complete clone is obtained from combining two graphs by identifying edges of of each original graph. We investigate how to change some properties such as height big height Krull dimension Betti numbers by gluing of two graphs at complete clone. We give a sufficient and necessary condition so that the glued graph of tw o Cohen-Macaulay chordal graphs at complete clone is a Cohen-Macaulay graph. Moreover we present the conditions that the edge ideal of gluing of two graphs at complete clone has linear resolution whenever the edge ideals of original graphs have linear resolution. We show when gluing of two independence complexes line graphs complement graphs can be expressed as independence complex line graph and complement of gluing of two graphs.

Key Words: Glued graph Height Big height Krull dimension Projective dimension Linear resolution Betti number Cohen-Macaulay.

INTRODUCTION

The concept edge ideal was first introduced by Villarreal in [23] that is let be a simple (no loops or multiple edges) graph on the vertex set and the edge set . Associate to is a quadratic square free monomial ideal with a field which is generated by such that . An approach to studying combinatorial properties of a graph is to examine some of algebraic invariants of the edge ideal. Indeed an aim of recent much research has been to create a dictionary between algebraic properties of and properties of .

In 2003 Uiyyasathain presented a new class of graphs in [19] glued graphs that is let and be any graphs and be non-trivial connected and such that with an isomorphism . The glued graph of and at and with respect to denoted by is as the graph that results from combining with by identifying and in the glued graph. In [15] Promsakon and Uiyyasathain characterized graph gluing between trees forests and bipartite graphs. Also they could give an upper bound of the chromatic number of glued graphs in terms of their original graphs. In [21] Uiyyasathain and Saduakdee studied the perfection of glued graphs at -clone. In [20] Uiyyasathain and Jongthawonwuth obtained bounds of the clique partition numbers of glued graph at -clones and -clones in terms of their original graphs. In [14] Pimpasalee and Uiyyasathain investigated bounds of clique covering numbers of glued graphs at -clones in terms of their original graphs.

As mentioned above the study of glued graphs from combinatorial points of view has become an active area but our main purpose of the current paper is to express algebraic features of glued graphs at complete clone using combinatorial properties. Also we have tried as much as possible to give an accurate description of some properties of a glued graph in terms of their original graphs. Furthermore we intend to verify whether the property of being Cohen- Macaulay Gorenstein (for chordal graphs) having linear resolution transfer from the glued graph to original graphs and vice versa. One of the main reasons for the importance of gluing of two graphs is the fact that this operation creates a larger class of graphs which one can obtain the results on the larger graph according to the information of the smaller graphs.

Our paper is organized as follows. In section 2 we give an explicit formula for computing the height of glued graph at complete clone. Also we present a lower bound for the big height of the glued graph at complete clone and characterize the glued graphs satisfying such bound. In section 3 we provide a necessary and sufficient condition which the equality holds for any We obtain explicit formulas for computing and also we present a lower bound for . We show that having linear resolution of the edge ideal of glued graph at complete clone implies that edge ideals of original graphs have linear resolution. A simple example illustrates having linear resolution the edge ideals of original graphs does not guarantee the existence of this property of the edge ideal of glued graph at complete clone then we present a necessary and sufficient condition for having linear resolution of the edge ideal of glued graph at complete clone.

For chordal graphs we provide the conditions that being Cohen- Macaulay preserves under operation gluing of two graphs at complete clone and vice versa. As a result we obtain a necessary and sufficient condition for being Gorenstein of gluing of two Cohen-Macaulay chordal graphs at complete clone. In Section 4 we give an upper bound for the projective dimension and Alexander dual of the edge ideal of the glued graph at any clone. For any two connected graphs containing a connected subgraph H we investigate the relation between the complement line graph and independence complex of the glued graph at clone and the complement line graph and independence complex of original graphs. Furthermore we determine a sufficient condition for vertex decomposability of the glued graph at any clone. In [16] it is proved that the glued graph of connected chordal graphs is chordal. The converse is not true in general.

We characterize a useful condition for being chordal of original graphs when the glued graph is chordal.

Equations

REFERENCES

1. M. Caboara S. Faridi and P. Selinger Simplicial cycles and the computation of simplicial trees J. Symbolic Computation 42 74-88(2007).

2. R. Chen Minimal free resolutions of linear edge ideals J. Algebra 324 3591-3613(2010).

3. CoCoATeam CoCoA: a system for doing Computations in Commutative Algebra Available at http://cocoa.dima.unige.it

4. N. Erey Bouquets vertex covers and the projective dimension of hypergraphs arxiv: 1402.3638v2(2014).

5. C. A. Francisco L. Klingler S. Sather-Wagstaff and J. Vassilev Progress in Commutative Algebra 1 Walter de Gruyter(2012).

6. C. A. Francisco and A. Van Tuyl Sequentially Cohen- Macaulay edge ideals Proc. Amer. Math. Soc. 135 no. 8 2327-2337 (electronic)(2007).

7. H. T. H A. Van Tuyl Monomial ideal edge ideals of hypergraphs and their graded Betti numbers J. Algebraic Combin 27 215- 245(2008).

8. H. T. H A. Van Tuyl Resolutions of square-free monomial ideals via facet ideals: a survey arxiv: math/0604301v2.

9. H. T. H A. Van Tuyl Splittable ideals and the resolutions of monomial ideals J. Algebra 309 405- 425(2007).

10. J. Herzog T. Hibi and X. Zheng Cohen-Macaulay chordal graphs J. Combin. Theory Ser. A 113 no. 5 911-916(2006).

11. S. Jacques Betti numbers of graph ideal PhD thesis University of Sheffield Great Britain(2004).

12. K. Kimura Non-vanishingness of Betti numbers of edge ideals Harmony of Gr bner bases and the modern industrial society 153168 World Sci. Publ. Hackensack NJ(2012).

13. H. Matsumura Commutative Ring Theory Cambridge tudies in Advanced Mathematics 8 Cambridge University Press(1986).

14. W. Pimpasalee C. Uiyyasathian Clique coverings of glued graphs at complete clones International Mathematical Forum 5 no.24 1155-1166(2010).

15. C. Promsakon C. Uiyyasathian Chromatic numbers of glued graphs Thai J. Math 4 no. 3 75-81(2006).

16. S. M. Seyyedi F. Rahmati Algebraic properties of pseudo-complete graphs Preprint.

17. S. M. Seyyedi F. Rahmati Study of algebraic properties of lollipop graphs Preprint.

18. N. Terai Alexander duality theorem and Stanley-Reisner rings Surikaisekikenkyusho Kokyu- ruko(1999) no. 1078 174184 Free resolutions of coordinate rings of projective varieties and related topics (Kyoto 1998).

19. C. Uiyyasathian Maximal-clique partitions PhD Thesis University of Colorado at Denver(2003).

20. C. Uiyyasathian U. Jongthawonwuth Clique partitions of glued graphs Journal of Mathematics Research 2 no. 2(2010).

21. C. Uiyyasathian S. Saduakdee Perfect glued graph at complete clones Journal of Mathematics Research 1 no. 1(2009).

22. R. H.Villarreal Combinatorial Optimization Methods in Commutative Algebra(2009) Preliminary version(2012).

23. R. H.Villarreal Cohen-Macaulay graphs Manuscripta Math 66 no. 3 277-293(1990).

24. R. H.Villarreal Monomial Algebras Monographs and Textbooks in Pure and Applied Mathematics 238 Marcel Dekker Inc New York (2001).

25. R.Woodroofe Chordal and sequentially Cohen-Macaulay clutters Electron. J. Combin18 no. 1 Paper 208 20 pages(2011).

26. X. Zheng Resolutions of facet ideals Comm. Algebra 32 2301-2324(2004).
COPYRIGHT 2015 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Publication:Science International
Article Type:Report
Date:Feb 28, 2015
Words:1340
Previous Article:INCLUSION OF NUCLEAR ENVELOPE IN NON-SPHERICAL CELLULAR GEOMETRY.
Next Article:STABILITY OF LINEAR REGRESSION MODELS.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters