Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome $alpha$-spectral extremal results for some digraphs
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
Visibility representation of digraphs was introduced by Axenovich, Beveridge, Hutch-inson, and West (emph{SIAM J. Discrete Math.} {bf 27}(3) (2013) 1429--1449) as a natural generalization of $t$-bar visibility representation of undirected graphs. A {it $t$-bar visibility representation} of a digraph $G$ assigns each vertex at most $t$ horizontal bars in the plane so that there is an arc $xy$ in the digraph if and only if some bar for $x$ sees some bar for $y$ above it along an unblocked vertical strip with positive width. The {it visibility number} $b(G)$ is the least $t$ such that $G$ has a $t$-bar visibility representation. In this paper, we solve several problems about $b(G)$ posed by Axenovich et al. and prove that determining whether the bar visibility number of a digraph is $2$ is NP-complete.
The $chi$-stability index ${rm es}_{chi}(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$. In this paper three open problems from [European J. Combin. 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$-regular ($kle 5$) graphs $G$ with ${rm es}_{chi}(G) = 1$ does not extend to $kge 6$. Graphs $G$ with $chi(G)=3$ for which ${rm es}_{chi}(G)+{rm es}_{chi}(overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${rm es}_{chi}(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $nequiv 2 pmod 3$ and $chi(G)=3$.
Let $D=(V,A)$ be an acyclic digraph. For $xin V$ define $e_{_{D}}(x)$ to be the difference of the indegree and the outdegree of $x$. An acyclic ordering of the vertices of $D$ is a one-to-one map $g: V rightarrow [1,|V|] $ that has the property that for all $x,yin V$ if $(x,y)in A$, then $g(x) < g(y)$. We prove that for every acyclic ordering $g$ of $D$ the following inequality holds: [sum_{xin V} e_{_{D}}(x)cdot g(x) ~geq~ frac{1}{2} sum_{xin V}[e_{_{D}}(x)]^2~.] The class of acyclic digraphs for which equality holds is determined as the class of comparbility digraphs of posets of order dimension two.
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.
Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $mathcal{F}$, we say that a hypergraph $H$ is Berge $mathcal{F}$-free if for every $F in mathcal{F}$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Tur{a}n-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
