共查询到20条相似文献,搜索用时 31 毫秒
1.
《Discrete Mathematics》2019,342(5):1275-1292
A discrete function of variables is a mapping , where , and are arbitrary finite sets. Function is called separable if there exist functions for , such that for every input the function takes one of the values . Given a discrete function , it is an interesting problem to ask whether is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of variables is known only for . In this paper we will show that a slightly more general recognition problem, when is not fully but only partially defined, is NP-complete for . We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for .The general recognition problem contains the above mentioned special case for . This case is well-studied in the context of game theory, where (separable) discrete functions of variables are referred to as (assignable) -person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of variables for any , thus generalizing the above result known for . Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function of variables one can construct separating functions in polynomial time with respect to the size of the input function. 相似文献
2.
A biased graph is a graph with a class of selected circles (“cycles”, “circuits”), called balanced, such that no theta subgraph contains exactly two balanced circles. A biased graph has two natural matroids, the frame matroid and the lift matroid , and their extensions the full frame matroid and the extended (or complete) lift matroid . In Part IV we used algebra to study the representations of these matroids by vectors over a skew field and the corresponding embeddings in Desarguesian projective spaces. Here we redevelop those representations, independently of Part IV and in greater generality, by using synthetic geometry. 相似文献
3.
4.
Given a simple graph with vertex set and edge set , the mixed graph is obtained from by orienting some of its edges. Let denote the Hermitian adjacency matrix of and be the adjacency matrix of . The -rank (resp. rank) of (resp. ), written as (resp. ), is the rank of (resp. ). Denote by the dimension of cycle space of , that is , where denotes the number of connected components of . In this paper, we concentrate on the relation between the -rank of and the rank of . We first show that for every mixed graph . Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently. 相似文献
5.
Irmina Czarna José-Luis Pérez Tomasz Rolski Kazutoshi Yamazaki 《Stochastic Processes and their Applications》2019,129(12):5406-5449
A level-dependent Lévy process solves the stochastic differential equation , where is a spectrally negative Lévy process. A special case is a multi-refracted Lévy process with . A general rate function that is non-decreasing and locally Lipschitz continuous is also considered. We discuss solutions of the above stochastic differential equation and investigate the so-called scale functions, which are counterparts of the scale functions from the theory of Lévy processes. We show how fluctuation identities for can be expressed via these scale functions. We demonstrate that the derivatives of the scale functions are solutions of Volterra integral equations. 相似文献
6.
《Discrete Mathematics》2019,342(5):1351-1360
We study functions defined on the vertices of the Hamming graphs . The adjacency matrix of has distinct eigenvalues with corresponding eigenspaces for . In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum for . For the case and we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case and we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for , and . In particular, we characterize eigenfunctions from the eigenspace with the minimum cardinality of the support for cases , and , . 相似文献
7.
Kai Wang 《Discrete Mathematics》2019,342(3):888-897
We present formulas to count the set of degree sequences of simple graphs of order , the set of degree sequences of those graphs with no isolated vertices, and the set of degree sequences of those graphs that are -connected for fixed . The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in and are asymptotically faster than previous known algorithms for these problems. We also show that and are asymptotically equivalent but and as well as and with fixed are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas. 相似文献
8.
9.
10.
《Discrete Mathematics》2019,342(2):344-351
Mader (2010) conjectured that for every positive integer and every finite tree with order , every -connected, finite graph with contains a subtree isomorphic to such that is -connected. The conjecture has been verified for paths, trees when , and stars or double-stars when . In this paper we verify the conjecture for two classes of trees when .For digraphs, Mader (2012) conjectured that every -connected digraph with minimum semi-degree for a positive integer has a dipath of order with . The conjecture has only been verified for the dipath with , and the dipath with and . In this paper, we prove that every strongly connected digraph with minimum semi-degree contains an oriented tree isomorphic to some given oriented stars or double-stars with order such that is still strongly connected. 相似文献
11.
For a graph , the -dominating graph of has vertices corresponding to the dominating sets of having cardinality at most , where two vertices of are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of by and , respectively, and the smallest integer for which is connected for all by . It is known that , but constructing a graph such that appears to be difficult.We present two related constructions. The first construction shows that for each integer and each integer such that , there exists a graph such that , and . The second construction shows that for each integer and each integer such that , there exists a graph such that , and . 相似文献
12.
《Discrete Mathematics》2020,343(7):111888
For any sequence , the extremal function is the maximum possible length of a -sparse sequence with distinct letters that avoids . We prove that if is an alternating sequence of length , then for all and , answering a question of Wellman and Pettie (2018) and extending the result of Roselle and Stanton that for any alternation of length (Roselle and Stanton, 1971).Wellman and Pettie also asked how large must be for there to exist -block sequences of length . We answer this question by showing that the maximum possible length of an -block sequence is if and only if . We also show related results for extremal functions of forbidden 0–1 matrices with any constant number of rows and extremal functions of forbidden sequences with any constant number of distinct letters. 相似文献
13.
We view an undirected graph as a symmetric digraph, where each edge is replaced by two opposite arcs and . Assume is an inverse closed subset of permutations of positive integers. We say is --colourable if for any mapping with , there is a mapping such that for each arc . The concept of --colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets such that every triangle-free planar graph is -3-colourable. Such a set is called TFP-good. Grötzsch’s theorem is equivalent to say that is TFP-good. We prove that for any inverse closed subset of which is not isomorphic to , is TFP-good if and only if either or there exists such that for each , . It remains an open question to determine whether or not is TFP-good. 相似文献
14.
15.
An independent broadcast on a connected graph is a function such that, for every vertex of , the value is at most the eccentricity of in , and implies that for every vertex of within distance at most from . The broadcast independence number of is the largest weight of an independent broadcast on . Clearly, is at least the independence number for every connected graph . Our main result implies . We prove a tight inequality and characterize all extremal graphs. 相似文献
16.
17.
Lionel Nguyen Van Thé 《Expositiones Mathematicae》2019,37(2):192-199
Say that a graph is representable in if there is a map from its vertex set into the Euclidean space such that iff and are both edges or both non-edges in . The purpose of this note is to present the proof of the following result, due to Einhorn and Schoenberg in Einhorn and Schoenberg (1966): if finite is neither complete nor independent, then it is representable in . A similar result also holds in the case of finite complete edge-colored graphs. 相似文献
18.
We consider the pseudo-Euclidean space , , with coordinates and metric , , where at least one is positive, and also tensors of the form , such that are differentiable functions of x. For such tensors, we use Lie point symmetries to find metrics that solve the Ricci curvature and the Einstein equations. We provide a large class of group-invariant solutions and examples of complete metrics defined globally in . As consequences, for certain functions , we show complete metrics , conformal to the pseudo-Euclidean metric g, whose scalar curvature is . 相似文献
19.
In this paper we study the existence of homomorphisms using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number for which there exists an assignment of unit vectors to its vertices such that when . Our approach allows to reprove, without using the Erdős–Ko–Rado Theorem, that for the Kneser graph and the -Kneser graph are cores, and furthermore, that for there exists a homomorphism if and only if divides . In terms of new applications, we show that the even-weight component of the distance -graph of the -cube is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms when . Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence’s list of strongly regular graphs (http://www.maths.gla.ac.uk/ es/srgraphs.php) and found that at least 84% are cores. 相似文献
20.
In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of and does there exist an -cycle decomposition of In this paper, the above question is answered for In fact, it is shown that the -fold line graph of the complete graph has a -decomposition if and only if and 相似文献