Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn some extremal position problems for graphs
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The general position number of a graph $G$ is the size of the largest set of vertices $S$ such that no geodesic of $G$ contains more than two elements of $S$. The monophonic position number of a graph is defined similarly, but with `induced path in place of `geodesic. In this paper we investigate some extremal problems for these parameters. Firstly we discuss the problem of the smallest possible order of a graph with given general and monophonic position numbers, with applications to a realisation result. We then solve a Tur{a}n problem for the size of graphs with given order and position numbers and characterise the possible diameters of graphs with given order and monophonic position number. Finally we classify the graphs with given order and diameter and largest possible general position number.
rate research
Read More
To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let $mathcal{G}(g,c,n)$ be the set of graphs $G$ with girth $g(G)=g$, circumference $c(G)=c$, and $n$ vertices; and let $mathcal{H}(g,c,m)$ be the set of graphs with girth $g$, circumference $c$, and $m$ edges. In this work, we study the four following extremal problems on graphs: $A(g,c,n)=min{delta(G),|; G in mathcal{G}(g,c,n) }$, $B(g,c,n)=max{delta(G),|; G in mathcal{G}(g,c,n) }$, $alpha(g,c,m)=min{delta(G),|; in mathcal{H}(g,c,m) }$ and $beta(g,c,m)=max{delta(G),|; G in mathcal{H}(g,c,m) }$. In particular, we obtain bounds for $A(g,c,n)$ and $alpha(g,c,m)$, and we compute the precise value of $B(g,c,n)$ and $beta(g,c,m)$ for all values of $g$, $c$, $n$ and $m$.
In this paper, we characterize the extremal digraphs with the maximal or minimal $alpha$-spectral radius among some digraph classes such as rose digraphs, generalized theta digraphs and tri-ring digraphs with given size $m$. These digraph classes are denoted by $mathcal{R}_{m}^k$, $widetilde{boldsymbol{Theta}}_k(m)$ and $INF(m)$ respectively. The main results about spectral extremal digraph by Guo and Liu in cite{MR2954483} and Li and Wang in cite{MR3777498} are generalized to $alpha$-spectral graph theory. As a by-product of our main results, an open problem in cite{MR3777498} is answered. Furthermore, we determine the digraphs with the first three minimal $alpha$-spectral radius among all strongly connected digraphs. Meanwhile, we determine the unique digraph with the fourth minimal $alpha$-spectral radius among all strongly connected digraphs for $0le alpha le frac{1}{2}$.
Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property $mathcal P$ and a graph $G$, the deficiency $text{def}(G)$ of the graph $G$ with respect to the property $mathcal P$ is the smallest non-negative integer $t$ such that the join $G*K_t$ has property $mathcal P$. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an $n$-vertex graph $G$ needs to ensure $G*K_t$ contains a $K_r$-factor (for any fixed $rgeq 3$). In this paper we resolve their problem fully. We also give an analogous result which forces $G*K_t$ to contain any fixed bipartite $(n+t)$-vertex graph of bounded degree and small bandwidth.
Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the local
A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cghs consisting of two disjoint triples. These were studied at length by Bra{ss} (2004) and by Aronov, Dujmovic, Morin, Ooms, and da Silveira (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of $n$ points in the plane.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
