RESEARCH

      Research Interests:  Graph theory, topological combinatorics and related fields

      Papers: Preprints, published--unpublished manuscripts and short notes : 


We prove that the (homological) connectivity of the independence complex of a hypergraph can be bounded in terms of its number of vertices and the Helly number of  its complementary hypergraph. Apart from that we provide an upper bound to the Leray number of noncover complexes of hypergraphs without any isolated vertex involving their strong domination numbers.


If G is a (finite and simple) graph, we call an independent set X gated if for every vertex x in X, there exists a neighbor y of x such that the set (X\{x})u{y} is also an independent set in G.  The gated independence number gi(G) is defined to be the maximum cardinality of a gated independent set in G. We demonstrate that the gated independence number is closely related to both matching and domination parameters of graphs. We prove that the inequalities mur(G)≥gi(G)≥im(G) hold for every graph G, where mur(G)  and im(G) are the uniquely restricted matching and induced matching  numbers of G. Furthermore, we provide bounds on the gated independence number involving the order, size and maximum degree. In particular, we prove that gi(G)≥n/5 for every n-vertex subcubic graph G without any isolated vertex and any component isomorphic to K_{3,3}, and 3n/8≥gi(B) for every n-vertex connected cubic bipartite graph B. 


          We study a new variation of a domination parameter defined over comparability graphs with a fixed transitive orientation. When P is a poset and Comp(P) its comparability graph, we call a dominating set D in Comp(P), order-sensitive , if it further respects the structure of P in the following sense: either x in D or else a<x<b in P for some a,b in D for each  element x in P which is neither maximal nor minimal. We prove that Roman domination and domination numbers of a graph as well as the total domination number of a bipartite graph can be realized as the order-sensitive domination number of posets associated to the  graph itself. We verify that order-sensitive domination number of a poset is equal to the biclique vertex-partition number of a bipartite graph constructed from P. (NB. The published version is slightly shorter than the local one. For instance, the former does not include the discussion on Helly posets as well as the complexity issue for the arbitrary height. Upon request, I may supply the longer corrected-local version.)


This is a (very) short note in which we prove that the domination number of a claw-free graph with minimum degree at least two is at most its edge domination number, generalizing an earlier result of Baste et al. on cubic claw-free graphs.


This resolves an open problem posed by Jaramillo and Villarreal in which it is proved that: for every positive integer k, there exists a connected graph H_k such that v(H_k)=reg(H_k)+k, where v(G) and reg(G) denote the v-number and the (Castelnuovo-Mumford) regularity of a graph G.


           We introduce and study a new invariant the M-number of graphs, and prove that the M-number of the independence complex of every graph is an upper bound to its collapsibility number. We show that the M-number, collapsibility and Leray numbers of a vertex decomposable graphs are equal. Moreover, we prove that the M-number of a graph G is closely related to its induced matching number im(G) as it happens to the Leray number of such complexes. We identify graph classes where they are equal, and otherwise provide upper bounds involving it. (NB.  Unfortunately, our earlier attempts to generalize the notion of the M-number to arbitrary simplicial complexes have  failed due to simple mistakes we made.  In the first draft, we falsely thought that such a number coincides with the collapsibility number, which is not the case. In the second, our justification of the primeness is wrong. Such an extension  is clearly well-defined and unified, which we believe it deserves further (possibly more careful) study. However, whether the notion of an M-prime vertex has its counterpart in the non-flag setting is still open. Therefore, we decide to narrow  its content to graphs.) 


          We prove that if G is a K_4-minor-free graph with maximum degree Δ≥3 and it contains no subgraph isomorphic to K_{2,r} for some positive integer r, then the square G2 of G is ( Δ+r)-colorable.


           This paper corresponds to the part two of the preprint arXiv:1503.06018  together with additional results in the final section. We demonstrate the effectiveness of prime graphs into the calculation of (Castelnuovo-Mumford) regularity of graphs. Such a notion allows us to reformulate the regularity as a generalized induced matching problem and perform the regularity calculations in specific graph classes. Apart from these, we prove that for each positive integer n, there exists a vertex decomposable perfect prime graph G(n) with reg(G(n))=n.   


        The paper has evolved from our arXiv preprint  arXiv:1503.06018 to which we have decided to divide it into two shorter papers due to its length. This is its first part having the same running title with the arXiv preprint. We present new combinatorial insights into the calculation of (Castelnuovo-Mumford) regularity of graphs. We introduce prime graphs wrt regularity that enables us to formulate the regularity as a generalized (weighted) induced matching problem. By analysing the effect of Lozin transformations on graphs, we narrow the search of prime graphs into bipartite graphs having sufficiently large girth with maximum degree at most three. We show that the regularity is monotone decreasing with respect to the contraction minor operation. Finally, we verify that for any pair (n,k) of positive integers, there exists a graph G(n,k) satisfying that reg(G(n,k))=n and im(G(n,k))=k. 


            The main purpose of this work is to explore Terai’s duality from the combinatorial point of view. On that direction, we prove that the projective dimension of any (hyper)graph can be bounded from above by  (Castelnuovo-Mumford) regularity of its Levi graph (or incidence bipartite graph). This in particular brings the use of regularity's upper bounds on the calculation of projective dimension of (hyper)graphs. When G is just a (simple) graph, we prove that there exists a (not necessarily induced) subgraph H of G such that proj-dim(H)=reg(S(G)), where S(G) is the subdivision graph of G. Moreover, we show that known upper bounds on proj-dim(G) involving domination parameters are in fact upper bounds to reg(S(G)). 

         This is a short note in which we show that when a graph G is codismantlable, then the codismantling order does not matter from which we produce a O(|V|^3/log|V|) running time algorithm for checking codismantlability by using Spinrad's data structure. Apart from that we introduce codismantlable posets, and prove that a poset P is codismantlable if and only if its comparability graph Comp(P) is. 


           We call a (simple) graph G codismantlable if either it has no edges or else it has a codominated vertex x, meaning that the closed neighborhood of x contains that of one of its neighbor, such that G-x codismantlable. We prove that if G is well-covered and it lacks induced cycles of length four, five and seven, than the vertex decomposability, codismantlability and Cohen-Macaulayness for G are all equivalent. The rest deals with the computation of Castelnuovo-Mumford regularity of codismantlable graphs. Note that our approach complements and unifies many of the earlier results on bipartite, chordal and very well-covered graphs. 


           We introduce a (hyper)graph operator on graphs that generalizes Kneser graph construction from complete graphs, and determine the chromatic, fractional chromatic and clique numbers of resulting graphs for a given fixed graph. By way of application, we construct graphs such that the gap between their chromatic and fractional chromatic numbers are arbitrarily large.  


         We prove that when a Lozin’s transformation is applied to a graph,  (Castelnuovo-Mumford) regularity of the graph increases exactly by one, as it happens to its induced matching number. As a consequence, we show that the regularity of a graph can be bounded from above by a function of its induced matching number. We also prove that the regularity of a graph is always less than or equal to the sum of its induced matching and decycling numbers. (NB. some of the results of this manuscript have appeared in here.)


             We introduce and study a class of simple graphs, the upper-maximal graphs (UM-graphs), associated to finite posets. The vertices of the UM-graph of a given poset P are the elements of P, and edges are formed by those vertices x and y whenever any maximal element of P that is greater than x is also greater than y or vice versa. We show that the class of UM-graphs constitutes a subclass of comparability graphs. We further provide a characterization of chordal UM-graphs, and compare UM-graphs with known bound graphs of posets. 


         We call a (simple) graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that the clique complexes of these graphs play a central role in the simple-homotopy theory of simplicial complexes. We prove that every (finite) simplicial complex is simple-homotopic to the clique complex of a 4-cycled graph. Apart from that we provide structural properties of 4-cycled graphs and introduce inductive operations (internal and external extensions) on graphs yielding 4-cycled graphs. Finally, we compute the homotopy type of external extensions of trees that result to be either contractible or homotopy equivalent to a wedge of spheres. 


          We introduce and study a class of simplicial complexes, the orphan complexes, associated to simple graphs whose families of (open or closed) vertex-neighborhoods are anti-Sperner. Under suitable restrictions, we show that the orphan complexes of these graphs are always shellable, and provide a characterization of graphs in terms of induced forbidden subgraphs contained in this restricted subfamily. 


          This is a short note aiming to introduce linear Sperner families and lattices and provide some open problems to interested readers.


           We introduce a combinatorial shifting operation on multicomplexes and study shiftings of linearly colored simplicial complexes. The operation carries similar properties required for an ordinary shifting operation, and the structure of linearly shifted complexes is easy to detect. For example, any such complex must be shellable. We also provide a way to compute (topological) Betti numbers of such complexes. As an application, we provide a characterization of simple graphs whose independence complexes are linearly shifted. The class of graphs obtained forms a superclass of threshold graphs. 


           This article introduces and studies linear colorings of simplicial complexes. We prove that any linearly colored complex can be strongly deformed to a subcomplex whose number of vertices exactly equals to the number of colors used. We also extend our work to include poset colorings and the colorings of complexes associated to simple graphs. 


           We study the enumeration problem of stably complex structures on bounded flag manifolds arising from omniorientations, and determine those induced by almost complex structures. We also enumerate the stably complex structures on these manifolds which bound, therefore representing zero in the complex cobordism ring. 


         The article considers the algebraic topology of certain sequences of toric manifolds, known as Bott towers. A simple decomposition is given of their suspensions into a wedge of Thom complexes, and the multiplicative structure of their real K-theory is deduced; the results are compared with those of Bahri and Bendersky (who used the Adams spectral sequence for additive calculations), and applied to the study of Bott towers in complex cobordism theory.  


          This article studies the geometry and topology of Bott towers in the context of toric geometry. We completely describe the associated fans of Bott towers arising from crosspolytopes. We deduce a description of the tangent bundle of the k th stage of the tower, considered as a complex manifold, which splits into a sum of complex line bundles. Applying Danilov-Jurkiewicz theorem, we compute the cohomology ring of any k th stage, and by way of construction, all the monomial identities defining the related affine toric varieties are given. 


        We generalize the notion of simpleness of a convex polytope to arbitrary finite posets by assuming that every element has a unique irredundant coatomic decomposition of certain length depending on its rank. Each such poset is equipped with a distinct lexicographical order on the set of its maximal chains induced by an ordering of coatoms. According to this ordering, we discuss the shelling of simple posets. Any simple poset carrying such a shelling is called coatomic shellable and it implies the ordinary CL-shellability of the poset.


            We exhibit an appropriate suspension of bounded flag manifolds as a wedge sum of Thom complexes of associated complex line bundles, and compute the real and complex K-groups. To achieve that we first compute Sq^2-homology of bounded flag manifolds to make use of relevant Atiyah-Hirzebruch spectral sequence of KO-theory.   


        This is a short note aiming to construct a smooth toric variety (uses Barnette sphere) which is not a toric manifold in the sense of Davis-Januszkiewicz. However, some proofs contain  mistakes (pointed by Professor Masuda, thanks to him), and I have never been able to correct them, so it has never surfaced since. The main result has been finally proven correctly by Y. Suyama .