Remarks on $D$-integral complete multipartite graphs

Pavel Híc; Milan Pokorný

Displaying similar documents to “Remarks on $D$ -integral complete multipartite graphs”

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

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

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

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.

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

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $γ (G)$ and $i (G)$ be the domination number and the independent domination number of $G$ , respectively. Rad and Volkmann posted a conjecture that $i (G) / γ (G) \leq Δ (G) / 2$ for any graph $G$ , where $Δ (G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $Δ (G) / 2$ are provided as well.

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

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.

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov (2003)

Fundamenta Mathematicae

Similarity:

For any collection of graphs $G ₁, . . ., G_{N}$ we find the minimal dimension d such that the product $G ₁ \times . . . \times G_{N}$ is embeddable into $ℝ^{d}$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $(K_{3, 3}) ⁿ$ are not embeddable into $ℝ^{2 n}$ , where K₅ and $K_{3, 3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $L k O \to S^{2 n - 1}$ , where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

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

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2, 2, r}$ r ∈ 4,5,6,7,8, $K_{2, 3, 4}$ , $K_{1 * 4, 4}$ , $K_{1 * 4, 5}$ , $K_{1 * 5, 4}$ . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2, 2, r}$ r ∈ 4,5,6,7,8, the others have been proved not...

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{A l l}$ , $E_{S o m e}$ , $E_{N o n e}$ of the edge set E, where: $E_{A l l}$ = e ∈ E, e belongs to all optimum solutions, $E_{N o n e}$ = e ∈ E, e does not belong to any optimum solution and $E_{S o m e}$ = e ∈ E, e belongs to some but not to all optimum solutions.

Displaying similar documents to “Remarks on D -integral complete multipartite graphs”

Displaying similar documents to “Remarks on $D$ -integral complete multipartite graphs”