Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPairs of a tree and a nontree graph with the same status sequence
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The status of a vertex $x$ in a graph is the sum of the distances between $x$ and all other vertices. Let $G$ be a connected graph. The status sequence of $G$ is the list of the statuses of all vertices arranged in nondecreasing order. $G$ is called status injective if all the statuses of its vertices are distinct. Let $G$ be a member of a family of graphs $mathscr{F}$ and let the status sequence of $G$ be $s.$ $G$ is said to be status unique in $mathscr{F}$ if $G$ is the unique graph in $mathscr{F}$ whose status sequence is $s.$ In 2011, J.L. Shang and C. Lin posed the following two conjectures. Conjecture 1: A tree and a nontree graph cannot have the same status sequence. Conjecture 2: Any status injective tree is status unique in all connected graphs. We settle these two conjectures negatively. For every integer $nge 10,$ we construct a tree $T_n$ and a unicyclic graph $U_n,$ both of order $n,$ with the following two properties: (1) $T_n$ and $U_n$ have the same status sequence; (2) for $nge 15,$ if $n$ is congruent to $3$ modulo $4$ then $T_n$ is status injective and among any four consecutive even orders, there is at least one order $n$ such that $T_n$ is status injective.
rate research
Read More
Let G be a simple connected graph of order n with degree sequence d_1, d_2, ..., d_n in non-increasing order. The spectral radius rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer L at most n, we give a sharp upper bound for rho(G) by a function of d_1, d_2, ..., d_L, which generalizes a series of previous results.
Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set ${x_1, ldots, x_n}$ of integers where $x_1<cdots<x_n$, let the {it gap sequence} of this set be the nondecreasing sequence $d_1, ldots, d_{n-1}$ where ${d_1, ldots, d_{n-1}}$ equals ${x_{i+1}-x_i:iin{1,ldots, n-1}}$ as a multiset. This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers $p$ and $q$, there is a positive integer $r_0$ such that for all $rgeq r_0$, the set of integers can be partitioned into $4$-sets with gap sequence $p, q$, $r$.
We consider orbit partitions of groups of automorphisms for the symplectic graph and apply Godsil-McKay switching. As a result, we find four families of strongly regular graphs with the same parameters as the symplectic graphs, including the one discovered by Abiad and Haemers. Also, we prove that switched graphs are non-isomorphic to each other by considering the number of common neighbors of three vertices.
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.$
The deck of a graph $G$ is the multiset of cards ${G-v:vin V(G)}$. Myrvold (1992) showed that the degree sequence of a graph on $ngeq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
