@article {1509, title = {Equimatchable claw-free graphs}, journal = {Discrete Mathematics}, volume = {341}, year = {2018}, pages = {2859-2871}, abstract = {

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 the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm.

}, keywords = {Connectivity, Equimatchable graph, Factor-critical}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2018.06.043}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X18302140}, author = {Saieed Akbari and Hadi Alizadeh and Ekim, Tinaz and Didem G{\"o}z{\"u}pek and Mordechai Shalom} } @article {1506, title = {A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs}, journal = {Information Processing Letters}, volume = {121}, year = {2017}, pages = {29-33}, abstract = {

It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.

}, keywords = {Graph algorithms, Maximum cut, Proper interval graph}, issn = {0020-0190}, doi = {https://doi.org/10.1016/j.ipl.2017.01.007}, url = {https://www.sciencedirect.com/science/article/pii/S0020019017300133}, author = {Arman Boyac{\i} and Ekim, Tinaz and Mordechai Shalom} } @article {1505, title = {On two extensions of equimatchable graphs}, journal = {Discrete Optimization}, volume = {26}, year = {2017}, pages = {112-130}, abstract = {

A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph G is said to be equimatchable if all maximal matchings of G saturating the set are of the same size. Noting that G is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters.

}, keywords = {Edge dominating set, Equimatchable graph, Gallai{\textendash}Edmonds decomposition, Minimum maximal matching, Parameterized complexity}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2017.08.002}, url = {https://www.sciencedirect.com/science/article/pii/S1572528616301438}, author = {Zakir Deniz and Ekim, Tinaz and Tatiana Romina Hartinger and Martin Milani{\v c} and Mordechai Shalom} } @article {1510, title = {Graphs of edge-intersecting and non-splitting paths}, journal = {Theoretical Computer Science}, volume = {629}, year = {2016}, pages = {40-50}, abstract = {

The families of Edge Intersection Graphs of Paths in a tree (resp. in a grid) EPT (resp. EPG) are well studied graph classes. Recently we introduced the class of graphs of Edge-Intersecting and Non-Splitting Paths in a Tree (ENPT) [5]. In this model, two vertices are adjacent if they represent two intersecting paths of a tree whose union is also a path. In this study we generalize this graph class by allowing the host graph to be an arbitrary graph. These are the graphs of Edge-Intersecting and Non-Splitting Paths ENP. Although the Edge Intersection Graphs of Paths in an arbitrary graph includes all graphs, we show that this is not the case for ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that such a restriction restricts the graph class. Specifically, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one.

}, keywords = {EPG graphs, EPT graphs, Intersection graphs}, issn = {0304-3975}, doi = {https://doi.org/10.1016/j.tcs.2015.10.004}, url = {https://www.sciencedirect.com/science/article/pii/S0304397515008750}, author = {Arman Boyac{\i} and Ekim, Tinaz and Mordechai Shalom and Shmuel Zaks} }