7 citations · 20 across the 23 of their papers we have counts for
13 papers · 1 filter
Perfect Graph Modification Problems: An Integer Programming Approach
Burak Nur Erdem, Tınaz Ekim, Zeki Caner Taşkın
Graph modification problems aim to find a small set of modifications to a graph so that it satisfies a desired property. The literature is rather rich in NP-completeness results an…
Generation of weighted trees, block trees and block graphs
Tınaz Ekim, Mordechai Shalom, Mehmet Aziz Yirik
We present a general framework to generate trees every vertex of which has a non-negative weight and a color. The colors are used to impose certain restrictions on the weight and c…
Defensive Domination in Proper Interval Graphs
Tınaz Ekim, Arthur Farley, Andrzej Proskurowski +1
-defensive domination, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on verti…
Well-indumatched Trees and Graphs of Bounded Girth
S. Akbari, T. Ekim, A. H. Ghodrati +1
A graph G is called well-indumatched if all of its maximal induced matchings have the same size. In this paper we characterize all well-indumatched trees. We provide a linear time…
Generation of random chordal graphs using subtrees of a tree
Oylum Şeker, Pinar Heggernes, Tınaz Ekim +1
Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many oth…
On Almost Well-Covered Graphs of Girth at Least 6
Tınaz Ekim, Didem Gözüpek, Ademir Hujdurović +1
We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-co…
Equimatchable Claw-Free Graphs
Saieed Akbari, Hadi Alizadeh, Tınaz Ekim +2
A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide, to t…
Edge-Stable Equimatchable Graphs
Zakir Deniz, Tınaz Ekim
A graph is \emph{equimatchable} if every maximal matching of has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the…
Improper Twin Edge Coloring of Graphs
Paniz Abedin, Saieed Akbari, Marc Demange +1
Let be a graph whose each component has order at least 3. Let for some integer be an improper edge coloring of (where adjacent…
The Maximum Cardinality Cut Problem is Polynomial in Proper Interval Graphs
Arman Boyacı, Tinaz Ekim, Mordechai Shalom
It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, a s…
Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersectin…
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge…
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Towards Hole Representations-Part I
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
Given a tree and a set of non-trivial simple paths on it, is the VPT graph (i.e. the vertex intersection graph) of the paths of the tree ,…