共查询到20条相似文献,搜索用时 46 毫秒
1.
Let Dn be the set of all signed permutations on [n] = {1,... ,n} with even signs, and let :Dn(T) be the set of all signed permutations in Dn which avoids a set T of signed patterns. In this paper, we find all the cardinalities of the sets Dn(T) where T B2. Some of the cardinalities encountered involve inverse binomial coefficients, binomial coefficients, Catalan numbers, and Fibonacci numbers. 相似文献
2.
符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$. 相似文献
3.
D. J. Grubb 《Transactions of the American Mathematical Society》1997,349(3):1081-1089
Let be a compact Hausdorff space and let denote the subsets of which are either open or closed. A quasi-linear functional is a map which is linear on singly generated subalgebras and such that for some . There is a one-to-one correspondence between the quasi-linear functional on and the set functions such that i) , ii) If with and disjoint, then , iii) There is an such that whenever are disjoint open sets, , and iv) if is open and , there is a compact such that whenever is open, then . The space of quasi-linear functionals is investigated and quasi-linear maps between two spaces are studied.
4.
Thomas Zaslavsky 《Discrete Applied Mathematics》1982,4(1):47-74
A signed graph is a graph with a sign attached to each arc. This article introduces the matroids of signed graphs, which generalize both the polygon matroids and the even-circle (or unoriented cycle) matroids of ordinary graphs. The concepts of balance, switching, restriction and contraction, double covering graphs, and linear representation of signed graphs are treated in terms of the matroid, and a matrix-tree theorem for signed graphs is proved. The examples treated include the all-positive and all-negative graphs (whose matroids are the polygon and even-circle matroids), sign-symmetric graphs (related to the classical root systems), and signed complete graphs (equivalent to two-graphs).Replacing the sign group by an arbitrary group leads to voltage graphs. Most of our results on signed graphs extend to all voltage graphs. 相似文献
5.
Thomas Zaslavsky 《Discrete Mathematics》1982,39(2):215-228
Coloring a signed graph by signed colors, one has a chromatic polynomial with the same enumerative and algebraic properties as for ordinary graphs. New phenomena are the interpretability only of odd arguments and the existence of a second chromatic polynomial counting zero-free colorings. The generalization to voltage graphs is outlined. 相似文献
6.
7.
《Discrete Mathematics》2022,345(3):112719
We answer a question of Brown and Jordon (2021) [4] by proving the existence of signed Langford sequences of every possible order for each defect. Our proof is constructive, and the constructions are shown to have other interesting properties and connections to several conjectures concerning permutations and partial sums of sequences of elements from cyclic groups. 相似文献
8.
A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E
+ and E
– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E
+ and E
– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde. 相似文献
9.
10.
11.
Lutz Volkmann 《Central European Journal of Mathematics》2014,12(3):517-528
Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α s k (G) of G. In this work, we mainly present upper bounds on α s k (G), as for example α s k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number. 相似文献
12.
ANDREJ MRVAR 《The Journal of mathematical sociology》2013,37(3):196-221
Structural balance theory forms the foundation for a generalized blockmodel method useful for delineating the structure of signed social one-mode networks for social actors (for example, people or nations). Heider's unit formation relation was dropped. We re-examine structural balance by formulating Heider's unit formation relations as signed two-mode data. Just as generalized blockmodeling has been extended to analyze two-mode unsigned data, we extend it to analyze signed two-mode network data and provide a formalization of the extension. The blockmodel structure for signed two-mode networks has positive and negative blocks, defined in terms of different partitions of rows and columns. These signed blocks can be located anywhere in the block model. We provide a motivating example and then use the new blockmodel type to delineate the voting patterns of the Supreme Court justices for all of their nonunanimous decisions for the 2006–07 term. Interpretations are presented together with a statement of further problems meriting attention for partitioning signed two-mode data. 相似文献
13.
本文首先引入Fuzzy集类上(广义)可加Fuzzy测度的有关概念,然后给出Fuzzy集上关于可加Fuzzy测度的Fuaay积分及有关定理,最后在一定条件下给出广义可加Fuzzy测度的一系列分解定理。 相似文献
15.
16.
17.
T. S. Michael 《Journal of Graph Theory》2002,41(2):101-105
We give necessary and sufficient conditions for the existence of a signed r‐multigraph with a prescribed signed degree sequence. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 101–105, 2002 相似文献
18.
《Advances in Applied Mathematics》2012,48(4):783-794
We show a simple connection between determinants and signed-excedance enumeration of permutations. This gives us an alternate proof of a result of Mantaci about enumerating signed excedances in permutations. The connection also gives an alternate proof of a result of Mantaci and Rakotondrajao about enumerating signed excedances over derangements.Motivated by this connection, we define several excedance-like statistics on permutations and show interesting values for their signed enumerator. In some cases, we also obtain the signed excedance-like statistic enumerator with respect to positive integral weights. 相似文献
19.
A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted αs2(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for αs2(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for αs2(T) are established and the extremal graphs characterized. It is shown that αs2(G) can be arbitrarily large negative even for a cubic graph G. 相似文献
20.
Thomas Lam 《Journal of Combinatorial Theory, Series A》2008,115(3):466-484
We study signed differential posets, a signed version of differential posets. These posets satisfy enumerative identities which are signed analogues of those satisfied by differential posets. Our main motivations are the sign-imbalance identities for partition shapes originally conjectured by Stanley, now proven in [T. Lam, Growth diagrams, domino insertion and sign-imbalance, J. Combin. Theory Ser. A 107 (2004) 87-115; A. Reifergerste, Permutation sign under the Robinson-Schensted-Knuth correspondence, Ann. Comb. 8 (2004) 103-112; J. Sjöstrand, On the sign-imbalance of partition shapes, J. Combin. Theory Ser. A 111 (2005) 190-203]. We show that these identities result from a signed differential poset structure on Young's lattice, and explain similar identities for Fibonacci shapes. 相似文献