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

Xiaoqian Liu; Xiaodan Chen; Junli Hu; Qiuyun Zhu

Displaying similar documents to “The extremal irregularity of connected graphs with given number of pendant vertices”

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

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

On the intersection graph of a finite group

Hossein Shahsavari, Behrooz Khosravi (2017)

Czechoslovak Mathematical Journal

Similarity:

For a finite group $G$ , the intersection graph of $G$ which is denoted by $Γ (G)$ is an undirected graph such that its 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 groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of $Aut (Γ (G))$ .

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu (2024)

Czechoslovak Mathematical Journal

Similarity:

The Turán number of a given graph $H$ , denoted by $ex (n, H)$ , is the maximum number of edges in an $H$ -free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $ex (n, K_{p} \cup K_{q}$ ) of a vertex-disjoint union of cliques $K_{p}$ and $K_{q}$ for all values of $n$ .

On the diameter of the intersection graph of a finite simple group

Xuanlong Ma (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group. The intersection graph $Δ_{G}$ of $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of $G$ , and two distinct vertices $X$ and $Y$ are adjacent if $X \cap Y \neq 1$ , where $1$ denotes the trivial subgroup of order $1$ . A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

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

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

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

Edge-sum distinguishing labeling

Jan Bok, Nikola Jedličková (2021)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We study edge-sum distinguishing labeling, a type of labeling recently introduced by Z. Tuza (2017) in context of labeling games. An ESD labeling of an $n$ -vertex graph $G$ is an injective mapping of integers $1$ to $l$ to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If $l$ equals to $n$ , we speak about a canonical ESD labeling. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not...

On the signless Laplacian and normalized signless Laplacian spreads of graphs

Emina Milovanović, Serife B. Bozkurt Altindağ, Marjan Matejić, Igor Milovanović (2023)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V, E)$ , $V = {v_{1}, v_{2}, ..., v_{n}}$ , be a simple connected graph with $n$ vertices, $m$ edges and a sequence of vertex degrees $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ . Denote by $A$ and $D$ the adjacency matrix and diagonal vertex degree matrix of $G$ , respectively. The signless Laplacian of $G$ is defined as $L^{+} = D + A$ and the normalized signless Laplacian matrix as $ℒ^{+} = D^{- 1 / 2} L^{+} D^{- 1 / 2}$ . The normalized signless Laplacian spreads of a connected nonbipartite graph $G$ are defined as $r (G) = γ_{2}^{+} / γ_{n}^{+}$ and $l (G) = γ_{2}^{+} - γ_{n}^{+}$ , where $γ_{1}^{+} \geq γ_{2}^{+} \geq \dots \geq γ_{n}^{+} \geq 0$ are eigenvalues of $ℒ^{+}$ . We establish sharp lower and upper bounds for the normalized signless...