Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe largest graphs with given order and diameter: A simple proof
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A consequence of Ores classic theorem characterizing the maximal graphs with given order and diameter is a determination of the largest such graphs. We give a very short and simple proof of this smaller result, based on a well-known elementary observation.
rate research
Read More
Sombor index is a novel topological index introduced by Gutman, defined as $SO(G)=sumlimits_{uvin E(G)}sqrt{d_{u}^{2}+d_{v}^{2}}$, where $d_{u}$ denotes the degree of vertex $u$. Recently, Chen et al. [H. Chen, W. Li, J. Wang, Extremal values on the Sombor index of trees, MATCH Commun. Math. Comput. Chem. 87 (2022), in press] considered the Sombor indices of trees with given diameter. For the continue, we determine the maximum Sombor indices for unicyclic graphs with given diameter.
Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let $G$ be a simple graph of order $n$ and $mu_1,mu_2,ldots,mu_n$ be the roots of its matching polynomial. The matching energy of $G$ is defined to be the sum of the absolute values of $mu_{i} (i=1,2,ldots,n)$. In this paper, we characterize the graphs with minimal matching energy among all unicyclic and bicyclic graphs with a given diameter $d$.
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, ldots, D_k$ such that $D_0=D$ and for any $iin {0, ldots, k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ldots cup D_i$. Denote the size of smallest $tau$-dynamic monopoly by $dyn_{tau}(G)$ and the average of thresholds in $tau$ by $overline{tau}$. We show that the values of $dyn_{tau}(G)$ over all assignments $tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{tau}(G)$ taken over all threshold assignments $tau$ with $overline{tau}leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
Let $G$ be a finite simple non-complete connected graph on ${1, ldots, n}$ and $kappa(G) geq 1$ its vertex connectivity. Let $f(G)$ denote the number of free vertices of $G$ and $mathrm{diam}(G)$ the diameter of $G$. Being motivated by the computation of the depth of the binomial edge ideal of $G$, the possible sequences $(n, q, f, d)$ of integers for which there is a finite simple non-complete connected graph $G$ on ${1, ldots, n}$ with $q = kappa(G), f = f(G), d = mathrm{diam}(G)$ satisfying $f + d = n + 2 - q$ will be determined. Furthermore, finite simple non-complete connected graphs $G$ on ${1, ldots, n}$ satisfying $f(G) + mathrm{diam}(G) = n + 2 - kappa(G)$ will be classified.
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
