اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe geometry connectivity of hypergraphs
88
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $mathcal{G}$ be a $k$-uniform hypergraph, $mathcal{L}_{mathcal{G}}$ be its Laplacian tensor. And $beta( mathcal{G})$ denotes the maximum number of linearly independent nonnegative eigenvectors of $mathcal{L}_{mathcal{G}}$ corresponding to the eigenvalue $0$. In this paper, $beta( mathcal{G})$ is called the geometry connectivity of $mathcal{G}$. We show that the number of connected components of $mathcal{G}$ equals the geometry connectivity $beta( mathcal{G})$.
قيم البحث
اقرأ أيضاً
Frankl and Furedi (1989) conjectured that the $r$-graph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest graph-Lagrangian of all $r$-graphs with $m$ edges. In this paper, we establish some
bounds for graph-Lagrangians of some special $r$-graphs that support this conjecture.
Since Cho and Kim (2005) showed that the competition graph of a doubly partial order is an interval graph, it has been actively studied whether or not the same phenomenon occurs for other variants of competition graph and interesting results have bee
n obtained. Continuing in the same spirit, we study the competition hypergraph, an interesting variant of the competition graph, of a doubly partial order. Though it turns out that the competition hypergraph of a doubly partial order is not always interval, we completely characterize the competition hypergraphs of doubly partial orders which are interval.
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with rep
lacement. It is easy to show that if $r geq r_c = 2^{k-1} ln 2 - (ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r leq r_c - 1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.
As a generalization of vertex connectivity, for connected graphs $G$ and $T$, the $T$-structure connectivity $kappa(G, T)$ (resp. $T$-substructure connectivity $kappa^{s}(G, T)$) of $G$ is the minimum cardinality of a set of subgraphs $F$ of $G$ that
each is isomorphic to $T$ (resp. to a connected subgraph of $T$) so that $G-F$ is disconnected. For $n$-dimensional hypercube $Q_{n}$, Lin et al. [6] showed $kappa(Q_{n},K_{1,1})=kappa^{s}(Q_{n},K_{1,1})=n-1$ and $kappa(Q_{n},K_{1,r})=kappa^{s}(Q_{n},K_{1,r})=lceilfrac{n}{2}rceil$ for $2leq rleq 3$ and $ngeq 3$. Sabir et al. [11] obtained that $kappa(Q_{n},K_{1,4})=kappa^{s}(Q_{n},K_{1,4})=lceilfrac{n}{2}rceil$ for $ngeq 6$, and for $n$-dimensional folded hypercube $FQ_{n}$, $kappa(FQ_{n},K_{1,1})=kappa^{s}(FQ_{n},K_{1,1})=n$, $kappa(FQ_{n},K_{1,r})=kappa^{s}(FQ_{n},K_{1,r})=lceilfrac{n+1}{2}rceil$ with $2leq rleq 3$ and $ngeq 7$. They proposed an open problem of determining $K_{1,r}$-structure connectivity of $Q_n$ and $FQ_n$ for general $r$. In this paper, we obtain that for each integer $rgeq 2$, $kappa(Q_{n};K_{1,r})=kappa^{s}(Q_{n};K_{1,r})=lceilfrac{n}{2}rceil$ and $kappa(FQ_{n};K_{1,r})=kappa^{s}(FQ_{n};K_{1,r})= lceilfrac{n+1}{2}rceil$ for all integers $n$ larger than $r$ in quare scale. For $4leq rleq 6$, we separately confirm the above result holds for $Q_n$ in the remaining cases.
An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the s
igned graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camions algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
