Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Boolean dimension of a graph and other related parameters
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions and the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.
rate research
Read More
Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted classes of posets. Bounded dimension gives a succinct representation of the poset, admitting constant response time for queries of the form is $x<y$?. This application motivates looking for stronger notions of dimension, possibly leading to succinct representations for more general classes of posets. We focus on two: boolean dimension, introduced in the 1980s and revisited in recent research, and local dimension, a very new one. We determine precisely which values of dimension/boolean dimension/local dimension imply that the two other parameters are bounded.
Let $mathbb{E}(H)$ and $mathbb{V}(H)$ denote the edge set and the vertex set of the simple connected graph $H$, respectively. The mixed metric dimension of the graph $H$ is the graph invariant, which is the mixture of two important graph parameters, the edge metric dimension and the metric dimension. In this article, we compute the mixed metric dimension for the two families of the plane graphs viz., the Web graph $mathbb{W}_{n}$ and the Prism allied graph $mathbb{D}_{n}^{t}$. We show that the mixed metric dimension is non-constant unbounded for these two families of the plane graph. Moreover, for the Web graph $mathbb{W}_{n}$ and the Prism allied graph $mathbb{D}_{n}^{t}$, we unveil that the mixed metric basis set $M_{G}^{m}$ is independent.
We present the structure theorem for the positive support of the cube of the Grover transition matrix of the discrete-time quantum walk (the Grover walk) on a general graph $G$ under same condition. Thus, we introduce a zeta function on the positive support of the cube of the Grover transition matrix of $G$, and present its Euler product and its determinant expression. As a corollary, we give the characteristic polynomial for the positive support of the cube of the Grover transition matrix of a regular graph, and so obtain its spectra. Finally, we present the poles and the radius of the convergence of this zeta function.
The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for trees. Motivated by a correspondence with Dasguptas objective for hierarchical clustering we consider the total rather than maximum depth of vertices as an alternative objective for minimization. For vertex partition trees this leads to a new parameter with a natural interpretation as a measure of robustness against vertex removal. As tools for the study of this family of parameters we show that they have similar recursive expressions and prove a binary tree rotation lemma. The new parameter is related to trivially perfect graph completion and therefore intractable like the other three are known to be. We give polynomial-time algorithms for both total-depth variants on caterpillars and on trees with a bounded number of leaf neighbors. For general trees, we obtain a 2-approximation algorithm.
In this paper we give structural characterizations of graphs not containing rooted $K_{4}$, $W_{4}$, $K_{2,4}$, and a graph we call $L$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
