ﻻ يوجد ملخص باللغة العربية
Let $t$ be a positive real number. A graph is called $t$-tough, if the removal of any cutset $S$ leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough, if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. In this paper we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the class of chordal graphs, split graphs, claw-free graphs and $2K_2$-free graphs.
Frei et al. [6] showed that the problem to decide whether a graph is stable with respect to some graph parameter under adding or removing either edges or vertices is $Theta_2^{text{P}}$-complete. They studied the common graph parameters $alpha$ (inde
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). Janos Pach (1981) answered this question in the negative. We strengthen this re
What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcal{G}$ as $nto infty$? We answer this question for a variety of sparse graph classes $mathcal{G}$. In particular, we show that the answer is $The
Given a family $mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $phicolon Ito mathcal{I}$ where for each $vin I$, $v$ is contained in $phi(v)$. Aharoni, Briggs, J. Kim, a
Let $T$ be a right exact functor from an abelian category $mathscr{B}$ into another abelian category $mathscr{A}$. Then there exists a functor ${bf p}$ from the product category $mathscr{A}timesmathscr{B}$ to the comma category $(Tdownarrowmathscr{A}