اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRecognising Graphic and Matroidal Connectivity Functions
89
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A {em connectivity function} on a set $E$ is a function $lambda:2^Erightarrow mathbb R$ such that $lambda(emptyset)=0$, that $lambda(X)=lambda(E-X)$ for all $Xsubseteq E$, and that $lambda(Xcap Y)+lambda(Xcup Y)leq lambda(X)+lambda(Y)$ for all $X,Y subseteq E$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. In this paper we give a method for identifying when a connectivity function comes from a graph. This method uses no more than a polynomial number of evaluations of the connectivity function. In contrast, we show that the problem of identifying when a connectivity function comes from a matroid cannot be solved in polynomial time. We also show that the problem of identifying when a connectivity function is not that of a matroid cannot be solved in polynomial time.
قيم البحث
اقرأ أيضاً
Let $M$ be a 3-connected matroid and let $mathbb F$ be a field. Let $A$ be a matrix over $mathbb F$ representing $M$ and let $(G,mathcal B)$ be a biased graph representing $M$. We characterize the relationship between $A$ and $(G,mathcal B)$, settlin
g four conjectures of Zaslavsky. We show that for each matrix representation $A$ and each biased graph representation $(G,mathcal B)$ of $M$, $A$ is projectively equivalent to a canonical matrix representation arising from $G$ as a gain graph over $mathbb F^+$ or $mathbb F^times$. Further, we show that the projective equivalence classes of matrix representations of $M$ are in one-to-one correspondence with the switching equivalence classes of gain graphs arising from $(G,mathcal B)$.
The class of quasi-graphic matroids recently introduced by Geelen, Gerards, and Whittle generalises each of the classes of frame matroids and lifted-graphic matroids introduced earlier by Zaslavsky. For each biased graph $(G, mathcal B)$ Zaslavsky de
fined a unique lift matroid $L(G, mathcal B)$ and a unique frame matroid $F(G, mathcal B)$, each on ground set $E(G)$. We show that in general there may be many quasi-graphic matroids on $E(G)$ and describe them all. We provide cryptomorphic descriptions in terms of subgraphs corresponding to circuits, cocircuits, independent sets, and bases. Equipped with these descriptions, we prove some results about quasi-graphic matroids. In particular, we provide alternate proofs that do not require 3-connectivity of two results of Geelen, Gerards, and Whittle for 3-connected matroids from their introductory paper: namely, that every quasi-graphic matroid linearly representable over a field is either lifted-graphic or frame, and that if a matroid $M$ has a framework with a loop that is not a loop of $M$ then $M$ is either lifted-graphic or frame. We also provide sufficient conditions for a quasi-graphic matroid to have a unique framework. Zaslavsky has asked for those matroids whose independent sets are contained in the collection of independent sets of $F(G, mathcal B)$ while containing those of $L(G, mathcal B)$, for some biased graph $(G, mathcal B)$. Adding a natural (and necessary) non-degeneracy condition defines a class of matroids, which we call biased graphic. We show that the class of biased graphic matroids almost coincides with the class of quasi-graphic matroids: every quasi-graphic matroid is biased graphic, and if $M$ is a biased graphic matroid that is not quasi-graphic then $M$ is a 2-sum of a frame matroid with one or more lifted-graphic matroids.
Lattice theory has been believed to resist classical computers and quantum computers. Since there are connections between traditional lattices and graphic lattices, it is meaningful to research graphic lattices. We define the so-called ice-flower sys
tems by our uncolored or colored leaf-splitting and leaf-coinciding operations. These ice-flower systems enable us to construct several star-graphic lattices. We use our star-graphic lattices to express some well-known results of graph theory and compute the number of elements of a particular star-graphic lattice. For more researching ice-flower systems and star-graphic lattices we propose Decomposition Number String Problem, finding strongly colored uniform ice-flower systems and connecting our star-graphic lattices with traditional lattices.
For an abelian group $Gamma$, a $Gamma$-labelled graph is a graph whose vertices are labelled by elements of $Gamma$. We prove that a certain collection of edge sets of a $Gamma$-labelled graph forms a delta-matroid, which we call a $Gamma$-graphic d
elta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by $k$ and Maximum Weight $S$-Tree Packing. We also discuss various properties of $Gamma$-graphic delta-matroids.
Let $pi_1=(d_1^{(1)}, ldots,d_n^{(1)})$ and $pi_2=(d_1^{(2)},ldots,d_n^{(2)})$ be graphic sequences. We say they emph{pack} if there exist edge-disjoint realizations $G_1$ and $G_2$ of $pi_1$ and $pi_2$, respectively, on vertex set ${v_1,dots,v_n}$ s
uch that for $jin{1,2}$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $iin{1,ldots,n}$. In this case, we say that $(G_1,G_2)$ is a $(pi_1,pi_2)$-textit{packing}. A clear necessary condition for graphic sequences $pi_1$ and $pi_2$ to pack is that $pi_1+pi_2$, their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is $NP$- complete. S.~Kundu proved in 1973 that if $pi_2$ is almost regular, that is each element is from ${k-1, k}$, then $pi_1$ and $pi_2$ pack if and only if $pi_1+pi_2$ is graphic. In this paper we will consider graphic sequences $pi$ with the property that $pi+mathbf{1}$ is graphic. By Kundus theorem, the sequences $pi$ and $mathbf{1}$ pack, and there exist edge-disjoint realizations $G$ and $mathcal{I}$, where $mathcal{I}$ is a 1-factor. We call such a $(pi,mathbf{1})$ packing a {em Kundu realization}. Assume that $pi$ is a graphic sequence, in which each term is at most $n/24$, that packs with $mathbf{1}$. This paper contains two results. On one hand, any two Kundu realizations of the degree sequence $pi+mathbf{1}$ can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of $pi+mathbf{1}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
