Zobrazeno 1 - 10
of 146
pro vyhledávání: '"Ekim, Tınaz"'
A set of vertices is $k$-sparse if it induces a graph with a maximum degree of at most $k$. In this missive, we consider the order of the largest $k$-sparse set in a triangle-free graph of fixed order. We show, for example, that every triangle-free g
Externí odkaz:
http://arxiv.org/abs/2406.03290
The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1] and [2], where some extremal graphs have also been provided. Then, a new question has emerged: how the maximum edge count is affected by for
Externí odkaz:
http://arxiv.org/abs/2304.01729
Determining the maximum number of edges under degree and matching number constraints have been solved for general graphs by Chv\'{a}tal and Hanson (1976), and by Balachandran and Khare (2009). It follows from the structure of those extremal graphs th
Externí odkaz:
http://arxiv.org/abs/2207.02271
Autor:
Deniz, Zakir, Ekim, Tınaz
A 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 harms the equimatchability, called edge-critical equimatchable graphs (ECE-graphs
Externí odkaz:
http://arxiv.org/abs/2202.07929
In this paper, we investigate a variant of Ramsey numbers called defective Ramsey numbers where cliques and independent sets are generalized to $k$-dense and $k$-sparse sets, both commonly called $k$-defective sets. We focus on the computation of def
Externí odkaz:
http://arxiv.org/abs/2107.12031
$k$-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 vertices of cardinality bounded by a parameter $k$. The problem has been sh
Externí odkaz:
http://arxiv.org/abs/2010.03865
A subset of vertices in a graph is called a total dominating set if every vertex of the graph is adjacent to at least one vertex of this set. A total dominating set is called minimal if it does not properly contain another total dominating set. In th
Externí odkaz:
http://arxiv.org/abs/2010.02341
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this paper, we give FPT algorithms for the maximum cardi
Externí odkaz:
http://arxiv.org/abs/2006.03856
Given a graph $G$, a $k$-sparse $j$-set is a set of $j$ vertices inducing a subgraph with maximum degree at most $k$. A $k$-dense $i$-set is a set of $i$ vertices that is $k$-sparse in the complement of $G$. As a generalization of Ramsey numbers, the
Externí odkaz:
http://arxiv.org/abs/1912.03705
It is known that any chordal graph on $n$ vertices can be represented as the intersection of $n$ subtrees in a tree on $n$ nodes. This fact is recently used in [2] to generate random chordal graphs on $n$ vertices by generating $n$ subtrees of a tree
Externí odkaz:
http://arxiv.org/abs/1904.04916