Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the convexity number of the complementary prism of a tree
183
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A set of vertices $S$ of a graph $G$ is a (geodesic)convex set, if $S$ contains all the vertices belonging to any shortest path connecting between two vertices of $S$. The cardinality of maximum proper convex set of $G$ is called the convexity number, con$(G)$ of $G$. The complementary prism $Gbar{G}$ of $G$ is obtained from the disjoint union of $G$ and its complement $bar{G}$ by adding the edges of a perfect matching between them. In this work, we examine the convex sets of the complementary prism of a tree and derive formulas for the convexity numbers of the complementary prisms of all trees.
rate research
Read More
An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. A $2$-matching is also called an induced matching. In this paper, we estimate the maximum number of $r$-matchings in a tree of fixed order. We also prove that the $n$-vertex path has the maximum number of induced matchings among all $n$-vertex trees.
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.$
Let $L(n,d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d.$ In 1975 Lesniak gave the lower bound $B(n,d)=lceil 2(n-1)/drceil$ for $L(n,d).$ When $d$ is even, $B(n,d)=L(n,d).$ But when $d$ is odd, $B(n,d)$ is smaller than $L(n,d)$ in general. For example, $B(21,3)=14$ while $L(21,3)=19.$ We prove that for $dge 2,$ $ L(n,d)=leftlceil frac{2(n-1)}{d}rightrceil$ if $d$ is even and $L(n,d)=leftlceil frac{2(n-2)}{d-1}rightrceil$ if $d$ is odd. The converse problem is also considered. Let $D(n,f)$ be the minimum possible diameter of a tree of order $n$ with exactly $f$ leaves. We prove that $D(n,f)=2$ if $n=f+1,$ $D(n,f)=2k+1$ if $n=kf+2,$ and $D(n,f)=2k+2$ if $kf+3le nle (k+1)f+1.$
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale-Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale-Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals.
Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwigers Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwigers Conjecture, we give a short proof that every $K_5$-minor-free graph has tree-chromatic number at most $4$, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
