Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the tree cover number and the positive semidefinite maximum nullity of a graph
62
0
0.0
(
0
)
Authors
Chassidy Bozeman
Ask ChatGPT about the research
No Arabic abstract
For a simple graph $G=(V,E),$ let $mathcal{S}_+(G)$ denote the set of real positive semidefinite matrices $A=(a_{ij})$ such that $a_{ij} eq 0$ if ${i,j}in E$ and $a_{ij}=0$ if ${i,j} otin E$. The maximum positive semidefinite nullity of $G$, denoted $operatorname{M}_+(G),$ is $max{operatorname{null}(A)|Ain mathcal{S}_+(G)}.$ A tree cover of $G$ is a collection of vertex-disjoint simple trees occurring as induced subgraphs of $G$ that cover all the vertices of $G$. The tree cover number of $G$, denoted $T(G)$, is the cardinality of a minimum tree cover. It is known that the tree cover number of a graph and the maximum positive semidefinite nullity of a graph are equal for outerplanar graphs, and it was conjectured in 2011 that $T(G)leq M_+(G)$ for all graphs [Barioli et al., Minimum semidefinite rank of outerplanar graphs and the tree cover number, $ Elec. J. Lin. Alg.,$ 2011]. We show that the conjecture is true for certain graph families. Furthermore, we prove bounds on $T(G)$ to show that if $G$ is a connected outerplanar graph on $ngeq 2$ vertices, then $operatorname{M}_+(G)=T(G)leq leftlceilfrac{n}{2}rightrceil$, and if $G$ is a connected outerplanar graph on $ngeq 6$ vertices with no three or four cycle, then $operatorname{M}_+(G)=T(G)leq frac{n}{3}$. We also characterize connected outerplanar graphs with $operatorname{M}_+(G)=T(G)=leftlceilfrac{n}{2}rightrceil.$
rate research
Read More
For a fixed planar graph $H$, let $operatorname{mathbf{N}}_{mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $operatorname{mathbf{N}}_{mathcal{P}}(n,C_m)$ is currently known for $min{3,4,5,6,8}$. In this note, we extend this list by establishing $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{10})sim(n/5)^5$ and $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{12})sim(n/6)^6$. We prove this by answering the following question for $min{5,6}$, which is interesting in its own right: which probability mass $mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $mu$ form an $m$-cycle?
Finding the maximum number of induced cycles of length $k$ in a graph on $n$ vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidick{y} and Pfender answered the question in the case $k=5$. In this paper we determine precisely, for all sufficiently large $n$, the maximum number of induced $5$-cycles that an $n$-vertex planar graph can contain.
The global forcing number of a graph G is the minimal cardinality of an edge subset discriminating all perfect matchings of G, denoted by gf(G). For any perfect matching M of G, the minimal cardinality of an edge subset S in E(G)-M such that G-S has a unique perfect matching is called the anti-forcing number of M,denoted by af(G, M). The maximum anti-forcing number of G among all perfect matchings is denoted by Af(G). It is known that the maximum anti-forcing number of a hexagonal system equals the famous Fries number. We are interested in some comparisons between the global forcing number and the maximum anti-forcing number of a graph. For a bipartite graph G, we show that gf(G)is larger than or equal to Af(G). Next we mainly extend such result to non-bipartite graphs, which is the set of all graphs with a perfect matching which contain no two disjoint odd cycles such that their deletion results in a subgraph with a perfect matching. For any such graph G, we also have gf(G) is larger than or equal to Af(G) by revealing further property of non-bipartite graphs with a unique perfect matching. As a consequence, this relation also holds for the graphs whose perfect matching polytopes consist of non-negative 1-regular vectors. In particular, for a brick G, de Carvalho, Lucchesi and Murty [4] showed that G satisfying the above condition if and only if G is solid, and if and only if its perfect matching polytope consists of non-negative 1-regular vectors. Finally, we obtain tight upper and lower bounds on gf(G)-Af(G). For a connected bipartite graph G with 2n vertices, we have that 0 leq gf(G)-Af(G) leq 1/2 (n-1)(n-2); For non-bipartite case, -1/2 (n^2-n-2) leq gf(G)-Af(G) leq (n-1)(n-2).
For a fixed set of positive integers $R$, we say $mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $mathcal{H}$ is emph{covering} if every vertex pair of $mathcal{H}$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $mathcal{H}$ is called a textit{Berge}-$G$, denoted by $BG$, if there exists an injection $f: E(G) to E(mathcal{H})$ such that for every $e in E(G)$, $e subseteq f(e)$. In this note, we define a new type of Ramsey number, namely the emph{cover Ramsey number}, denoted as $hat{R}^R(BG_1, BG_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $mathcal{H}$ on $n geq n_0$ vertices and every $2$-edge-coloring (blue and red) of $mathcal{H}$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $kgeq 2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1, G_2) leq hat{R}^{[k]}(BG_1, BG_2) leq c_k cdot R(G_1, G_2)^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c = c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $hat{R}^{[k]}(BG,BG) leq cn$.
A graph $X$ is said to be unstable if the direct product $X times K_2$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$. It is nontrivially unstable if it is unstable, connected, and nonbipartite, and no two distinct vertices of X have exactly the same neighbors. We find three new conditions that each imply a circulant graph is unstable. (These yield infinite families of nontrivially unstable circulant graphs that were not previously known.) We also find all of the nontrivially unstable circulant graphs of order $2p$, where $p$ is any prime number. Our results imply that there does not exist a nontrivially unstable circulant graph of order $n$ if and only if either $n$ is odd, or $n < 8$, or $n = 2p$, for some prime number $p$ that is congruent to $3$ modulo $4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
