Algebraic connectivity of $k$-connected graphs

Stephen J. Kirkland; Israel Rocha; Vilmar Trevisan

Displaying similar documents to “Algebraic connectivity of $k$ -connected 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$ .

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

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal 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...

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.

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

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

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number $γ_{p r} (G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .

Characterization by intersection graph of some families of finite nonsimple groups

Hossein Shahsavari, Behrooz Khosravi (2021)

Czechoslovak Mathematical Journal

Similarity:

For a finite group $G$ , $Γ (G)$ , the intersection graph of $G$ , is a simple graph whose vertices are all nontrivial proper subgroups of $G$ and two distinct vertices $H$ and $K$ are adjacent when $H \cap K \neq 1$ . In this paper, we classify all finite nonsimple groups whose intersection graphs have a leaf and also we discuss the characterizability of them using their intersection graphs.

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

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

Displaying similar documents to “Algebraic connectivity of k -connected graphs”

Displaying similar documents to “Algebraic connectivity of $k$ -connected graphs”