Domination numbers in graphs with removed edge or set of edges

Magdalena Lemańska

Displaying similar documents to “Domination numbers in graphs with removed edge or set of edges”

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

Does the endomorphism poset $P^{P}$ determine whether a finite poset $P$ is connected? An issue Duffus raised in 1978

Jonathan David Farley (2023)

Mathematica Bohemica

Similarity:

Duffus wrote in his 1978 Ph.D. thesis, “It is not obvious that $P$ is connected and $P^{P} ≅ Q^{Q}$ imply that $Q$ is connected”, where $P$ and $Q$ are finite nonempty posets. We show that, indeed, under these hypotheses $Q$ is connected and $P ≅ Q$ .

On D-connected sets in the space $V^{q}$

S. Topa (1976)

Annales Polonici Mathematici

Similarity:

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph $G$ , denoted by $L (G)$ , has $E (G)$ as its vertex set, where two vertices in $L (G)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$ , define ${\bar{σ}}_{2} (H) = min {d (u) + d (v) : u v \in E (H)}$ . Let $H$ be a 2-connected claw-free simple graph of order $n$ with $δ (H) \geq 3$ . We show that, if ${\bar{σ}}_{2} (H) \geq \frac{1}{7} (2 n - 5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $cl (H) = L (G)$ , where $G$ is an essentially $2$ -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

Similarity:

An edge of $G$ is singular if it does not lie on any triangle of $G$ ; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G [N (u)]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such...

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized $k$ -connectivity $κ_{k} (G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$ -edge-connectivity which is defined as $λ_{k} (G) = min {λ (S) : S \subseteq V (G)$ and $| S | = k}$ , where $λ (S)$ denotes the maximum number $ℓ$ of pairwise edge-disjoint trees $T_{1}, T_{2}, ..., T_{ℓ}$ in $G$ such that $S \subseteq V (T_{i})$ for $1 \leq i \leq ℓ$ . In this paper we prove that for any two connected graphs $G$ and $H$ we have $λ_{3} (G □ H) \geq λ_{3} (G) + λ_{3} (H)$ , where $G □ H$ is the Cartesian product of $G$ and $H$ . Moreover, the bound is sharp. We also...

Even factor of bridgeless graphs containing two specified edges

Nastaran Haghparast, Dariush Kiani (2018)

Czechoslovak Mathematical Journal

Similarity:

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$ . Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_{1}$ and $e_{2}$ of $G$ , there is an even factor containing $e_{1}$ and $e_{2}$ ...

On the bounds of Laplacian eigenvalues of $k$ -connected graphs

Xiaodan Chen, Yaoping Hou (2015)

Czechoslovak Mathematical Journal

Similarity:

Let $μ_{n - 1} (G)$ be the algebraic connectivity, and let $μ_{1} (G)$ be the Laplacian spectral radius of a $k$ -connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $μ_{n - 1} (G) \geq \frac{2 n k^{2}}{(n (n - 1) - 2 m) (n + k - 2) + 2 k^{2}},$ with equality if and only if $G$ is the complete graph $K_{n}$ or $K_{n} - e$ . Moreover, if $G$ is non-regular, then $μ_{1} (G) < 2 Δ - \frac{2 (n Δ - 2 m) k^{2}}{2 (n Δ - 2 m) (n^{2} - 2 n + 2 k) + n k^{2}},$ where $Δ$ stands for the maximum degree of $G$ . Remark that in some cases, these two inequalities improve some previously known results.