A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang; Bing Wei

Displaying similar documents to “A note on the independent domination number versus the domination number in bipartite graphs”

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g (n, l)$ , the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$ . By edit distance of two graphs $G$ , $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$ . This new extremal number $g (n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Note on a conjecture for the sum of signless Laplacian eigenvalues

Xiaodan Chen, Guoliang Hao, Dequan Jin, Jingjian Li (2018)

Czechoslovak Mathematical Journal

Similarity:

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1 \leq k \leq n$ , denote by $𝒮_{k}^{+} (G)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$ . It was conjectured that $𝒮_{k}^{+} (G) \leq e (G) + (\binom{k + 1}{2})$ , where $e (G)$ is the number of edges of $G$ . This conjecture has been proved to be true for all graphs when $k \in {1, 2, n - 1, n}$ , and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$ ). In this note, this conjecture is proved to be true for all graphs when $k = n - 2$ , and for some new classes of graphs.

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...

Note on improper coloring of $1$ -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph $G = (V, E)$ is called improperly $(d_{1}, \dots, d_{k})$ -colorable if the vertex set $V$ can be partitioned into subsets $V_{1}, \dots, V_{k}$ such that the graph $G [V_{i}]$ induced by the vertices of $V_{i}$ has maximum degree at most $d_{i}$ for all $1 \leq i \leq k$ . In this paper, we mainly study the improper coloring of $1$ -planar graphs and show that $1$ -planar graphs with girth at least $7$ are $(2, 0, 0, 0)$ -colorable.

Saturation numbers for linear forests $P_{6} + t P_{2}$

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is $H$ -saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$ . The saturation number, $sat (n, H)$ , is the minimum number of edges of a graph in the set of all $H$ -saturated graphs of order $n$ . We determine the saturation number $sat (n, P_{6} + t P_{2})$ for $n \geq \frac{10}{3} t + 10$ and characterize the extremal graphs for $n > \frac{10}{3} t + 20$ .

Intrinsic linking and knotting are arbitrarily complex

Erica Flapan, Blake Mellor, Ramin Naimi (2008)

Fundamenta Mathematicae

Similarity:

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, $| l k (Q_{i}, Q_{j}) | \geq α$ and $| a ₂ (Q_{i}) | \geq α$ , where $a ₂ (Q_{i})$ denotes the second coefficient of the Conway polynomial of $Q_{i}$ .

On the multiplicity of Laplacian eigenvalues for unicyclic graphs

Fei Wen, Qiongxiang Huang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a connected graph of order $n$ and $U$ a unicyclic graph with the same order. We firstly give a sharp bound for $m_{G} (μ)$ , the multiplicity of a Laplacian eigenvalue $μ$ of $G$ . As a straightforward result, $m_{U} (1) \leq n - 2$ . We then provide two graph operations (i.e., grafting and shifting) on graph $G$ for which the value of $m_{G} (1)$ is nondecreasing. As applications, we get the distribution of $m_{U} (1)$ for unicyclic graphs on $n$ vertices. Moreover, for the two largest possible values of $m_{U} (1) \in {n - 5, n - 3}$ , the corresponding graphs $U$ are...

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...

Maximum bipartite subgraphs in $H$ -free graphs

Jing Lin (2022)

Czechoslovak Mathematical Journal

Similarity:

Given a graph $G$ , let $f (G)$ denote the maximum number of edges in a bipartite subgraph of $G$ . Given a fixed graph $H$ and a positive integer $m$ , let $f (m, H)$ denote the minimum possible cardinality of $f (G)$ , as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$ . In this paper we prove that $f (m, θ_{k, s}) \geq \frac{1}{2} m + Ω (m^{(2 k + 1) / (2 k + 2)})$ , which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_{k}^{'}$ and $K_{t, s}^{'}$ for the subdivisions of $K_{k}$ and $K_{t, s}$ . We show that $f (m, K_{k}^{'}) \geq \frac{1}{2} m + Ω (m^{(5 k - 8) / (6 k - 10)})$ and $f (m, K_{t, s}^{'}) \geq \frac{1}{2} m + Ω (m^{(5 t - 1) / (6 t - 2)})$ , improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

A note on the double Roman domination number of graphs

Xue-Gang Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

For a graph $G = (V, E)$ , a double Roman dominating function is a function $f : V \to {0, 1, 2, 3}$ having the property that if $f (v) = 0$ , then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f (w) = 3$ , and if $f (v) = 1$ , then the vertex $v$ must have at least one neighbor with $f (w) \geq 2$ . The weight of a double Roman dominating function $f$ is the sum $f (V) = \sum_{v \in V} f (v)$ . The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by $γ_{dR} (G)$ . In this paper, we establish a new...

On the domination of triangulated discs

Noor A&amp;#039;lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili (2023)

Mathematica Bohemica

Similarity:

Let $G$ be a $3$ -connected triangulated disc of order $n$ with the boundary cycle $C$ of the outer face of $G$ . Tokunaga (2013) conjectured that $G$ has a dominating set of cardinality at most $\frac{1}{4} (n + 2)$ . This conjecture is proved in Tokunaga (2020) for $G - C$ being a tree. In this paper we prove the above conjecture for $G - C$ being a unicyclic graph. We also deduce some bounds for the double domination number, total domination number and double total domination number in triangulated discs.

Generalized connectivity of some total graphs

Yinkui Li, Yaping Mao, Zhao Wang, Zongtian Wei (2021)

Czechoslovak Mathematical Journal

Similarity:

We study the generalized $k$ -connectivity $κ_{k} (G)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$ -edge-connectivity $λ_{k} (G)$ . We determine the exact value of $κ_{k} (G)$ and $λ_{k} (G)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k = 3$ .