Yazar "Deniz, Zakir" seçeneğine göre listele
Listeleniyor 1 - 13 / 13
Sayfa Başına Sonuç
Sıralama seçenekleri
Öğe Bounding the chromatic number of squares of K-4-minor-free graphs(Elsevier Science Bv, 2019) Civan, Yusuf; Deniz, Zakir; Yetim, Mehmet AkifLet G be a K-4-minor-free graph with Delta(G) >= 3. We prove that if G contains no subgraph isomorphic to K-2(,r) for some r >= 1. then chi(G(2)) <= Delta(G) + r. (C) 2019 Elsevier B.V. All rights reserved.Öğe A classification of 1-well-covered graphs(Scientific Technical Research Council Turkey-Tubitak, 2021) Deniz, ZakirA graph is well-covered if all its maximal independent sets have the same size. If a graph is well-covered and remains well-covered upon removal of any vertex, then it is called 1-well-covered graph. It is well-known that [n/2] + 1 <= alpha(G) mu(G) <= n for any graph G with n vertices where alpha(G) and mu(G) are the independence and matching numbers of G, respectively. A graph G satisfying alpha(G) + mu(G) = n is known as Konig-Egervary graph, and such graphs are characterized by Levit and Mandrescu [14] under the assumption that G is 1-well-covered. In this paper, we investigate connected 1-well-covered graphs with respect to alpha(G) + mu(G) = n - k for k >= 1 and vertical bar G vertical bar = n. We further present some combinatorial properties of such graphs. In particular, we provide a tight upper bound on the size of those graphs in terms of k, namely vertical bar G vertical bar <= 10k - 2, also we show that Delta(G) <= 2k + 1 and alpha(G) <= min{4k - 1,n - 2k}. This particularly enables us to obtain a characterization of such graphs for k = 1, which settles a problem of Levit and Mandrescu [14].Öğe Critical equimatchable graphs(Centre Discrete Mathematics & Computing, 2024) Deniz, Zakir; Ekim, TinazA graph G is equimatchable if every maximal matching of G has the same cardinality. In this paper, we investigate equimatchable graphs such that the removal of any edge creates a graph that is not equimatchable, called edge -critical equimatchable graphs (ECE-graphs). We show that apart from two simple cases, namely bipartite ECE-graphs and even cliques, all ECE-graphs are 2 -connected factor -critical. Accordingly, we give a characterization of factor -critical ECE-graphs with connectivity 2. Our result provides a partial answer to an open question posed by Levit and Mandrescu [Eur. J. Comb. 20 (2019), 261-272] on the characterization of wellcovered graphs with no shedding vertex. We also introduce equimatchable graphs such that the removal of any vertex creates a graph that is not equimatchable, called vertex -critical equimatchable graphs (VCE- graphs). To conclude, we clarify the relationship between various subclasses of equimatchable graphs (including ECE-graphs and VCE-graphs) and discuss the properties of factor -critical ECE-graphs with connectivity at least 3.Öğe Domination versus edge domination on claw-free graphs(Elsevier, 2023) Civan, Yusuf; Deniz, Zakir; Yetim, Mehmet AkifWhen G is a (finite and simple) graph, we prove that its domination number is at most its edge-domination number if G is a claw-free graph with minimum degree at least two. That generalizes an earlier result of Baste et al. (2020) on cubic claw-free graphs.(c) 2023 Elsevier B.V. All rights reserved.Öğe Edge-stable equimatchable graphs(Elsevier Science Bv, 2019) Deniz, Zakir; Ekim, TınazA graph G is equimatchable if every maximal matching of G has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the graph preserves the equimatchability. We call an equimatchable graph G edge-stable if G \ e, that is the graph obtained by the removal of edge e from G, is also equimatchable for any e is an element of E(G). After noticing that edge-stable equimatchable graphs are either 2-connected factor-critical or bipartite, we characterize edge-stable equimatchable graphs. This characterization yields an O(min(n(3.376), n(1.5)m)) time recognition algorithm. Lastly, we introduce and shortly discuss the related notions of edge-critical, vertex-stable and vertex critical equimatchable graphs. In particular, we emphasize the links between our work and the well-studied notion of shedding vertices, and point out some open questions. (C) 2018 Elsevier B.V. All rights reserved.Öğe Gated independence in graphs(Elsevier, 2024) Civan, Yusuf; Deniz, Zakir; Yetim, Mehmet AkifIf G = ( V , E ) is a (finite and simple) graph, we call an independent set X a gated independent set in G if for each x is an element of X , there exists a neighbor y of x such that ( X \ { x } ) boolean OR{ y } is an independent set in G . We define the gated independence number gi( G ) of G 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 im( G ) gi( G ) m ur ( G ) hold for every graph G , where im( G ) and m ur ( G ) denote the induced and uniquely restricted matching numbers of G . On the other hand, we show that gamma i ( G ) gi( G ) and gamma p r ( G ) 2 gi( G ) for every graph G without any isolated vertex, where gamma i ( G ) and gamma p r ( G ) denote the independence and paired domination numbers. Furthermore, we provide bounds on the gated independence number involving the order, size and maximum degree. In particular, we prove that gi( G ) 5 n for every n -vertex subcubic graph G without any isolated vertex or any component isomorphic to K 3 , 3 , and gi( B ) 3 n 8 for every n -vertex connected cubic bipartite graph B . (c) 2024 Elsevier B.V. All rights reserved.Öğe On contact graphs of paths on a grid(Springer Verlag, 2018) Deniz, Zakir; Galby, Esther; Munaro, Andrea; Ries, BernardIn this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B0-CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG. © Springer Nature Switzerland AG 2018.Öğe On graphs admitting two disjoint maximum independent sets(University of Primorska, 2023) Deniz, Zakir; Levit, V.E.; Mandrescu, E.An independent set S is maximal if it is not a proper subset of an independent set, while S is maximum if it has a maximum size. The problem of whether a graph has a pair of disjoint maximal independent sets was introduced by Berge in the early 1970s. The class of graphs for which every induced subgraph admits two disjoint maximal independent sets was characterized by Schaudt in 2015. In this paper, we are focused on finding conditions ensuring the existence of two disjoint maximum independent sets. © 2022 Colegio Oficial de la Psicología de Madrid.Öğe On Split B-1-EPG Graphs(Springer International Publishing Ag, 2018) Deniz, Zakir; Nivelle, Simon; Ries, Bernard; Schindl, DavidIn this paper, we are interested in edge intersection graphs of paths in a grid, such that each such path has at most one bend. These graphs were introduced in [12] and they are called B-1-EPG graphs. In particular, we focus on split graphs and characterise those that are B-1-EPG. This characterisation allows us to disprove a conjecture of Cameron et al. [7]. The existence of polynomial-time recognition algorithm for this graph class is still unknown. We furthermore investigate inclusion relationships among subclasses of split graphs that are B-1-EPG.Öğe ON THE WELL-COVEREDNESS OF SQUARE GRAPHS(Ankara Univ, Fac Sci, 2022) Deniz, ZakirThe square of a graph G is obtained from G by putting an edge between two distinct vertices whenever their distance in G is 2. A graph is well-covered if every maximal independent set in the graph is of the same size. In this paper, we investigate the graphs whose squares are well-covered. We first provide a characterization of the trees whose squares are well-covered. Afterwards, we show that a bipartite graph G and its square are well-covered if and only if every component of G is K-1 or K-r,K-r for some r >= 1. Moreover, we obtain a characterization of the graphs whose squares are well-covered in the case alpha(G) = alpha(G(2)) + k for k is an element of {0, 1}.Öğe Order-Sensitive Domination in Partially Ordered Sets and Graphs(Springer, 2022) Civan, Yusuf; Deniz, Zakir; Yetim, Mehmet AkifFor a (finite) partially ordered set (poset) P, we call a dominating set D in the comparability graph of P, an order-sensitive dominating set in P if either x is an element of D or else a < x < b in P for some a,b is an element of D for every element x in P which is neither maximal nor minimal, and denote by gamma(os)(P), the least size of an order-sensitive dominating set of P. For every graph G and integer k >= 2, we associate to G a graded poset P-k(G) of height k, and prove that gamma(os)(P-3(G)) = gamma(R)(G) and gamma(os)(P-4(G)) = 2 gamma(G) hold, where gamma(G) and gamma(R)(G) are the domination and Roman domination number of G respectively. Moreover, we show that the order-sensitive domination number of a poset P exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of P.Öğe Sectionable Tournaments: their Topology and Coloring(Springer, 2022) Deniz, ZakirWe provide a detailed study of topological and combinatorial properties of sectionable tournaments. This class forms an inductively constructed family of tournaments grounded over simply disconnected tournaments, those tournaments whose fundamental groups of acyclic complexes are non-trivial. When T is a sectionable tournament, we fully describe the cell-structure of its acyclic complex Acy(T) by using the adapted machinery of discrete Morse theory for acyclic complexes of tournaments. In the combinatorial side, we demonstrate that the dimension of the complex Acy(T) has a role to play. We prove that if T is a (2r + 1)-sectionable tournament and d is the dimension of Acy(T), then the (acyclic) chromatic number of T satisfies chi(T)<= 2(2-1/(r+1))(log(d+1))-1 where the logarithm has two as its base.Öğe Some results on 2-distance coloring of planar graphs with girth five(Springer, 2024) Deniz, ZakirA vertex coloring of a graph G is called a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors. Suppose that G is a planar graph with girth 5 and maximum degree Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document}. We prove that G admits a 2-distance Delta+7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta +7$$\end{document} coloring, which improves the result of Dong and Lin (J Comb Optim 32(2):645-655, 2016). Moreover, we prove that G admits a 2-distance Delta+6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta +6$$\end{document} coloring when Delta >= 10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \ge 10$$\end{document}.
