A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

A graph partition problem

ＡＧＲＡＰＨＰＡＲＴＩＴＩＯＮＰＲＯＢＬＥＭ￥ＬＩＵＴＡＮＰＥＩ（刘彦佩）（ＤｅｐａｒｆｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｔｈｅｒｎＪｉａｏｔｏｎｙＵｎｉｖｅｒｓｉｔｙ,Ｂｅｉｊｉｎｇ１０００４４,Ｃｈｉｎａ）ＡＵＲＯＲＡＭＯＲＧＡＮＡ（Ｄｅ...     

Calculus on strong partition cardinals

In [1] it was shown that if κ is a strong partition cardinal, then every function from [κ ]^κ to [κ ]^κ is continuous almost everywhere. In this investigation, we explore whether such functions are differentiable or integrable in any sense. Some of them are. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on selective line-graphs and partition colorings

We extend a one-to-one correspondence between the set of all colorings of any graph and the set of all stable sets of an auxiliary graph, from graphs to partitioned graphs. This correspondence has an application to Selective Coloring and to Selective Max-Coloring.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

The partition problem

In this paper we describe several forms of thek-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.Partial Support from NSF Grants DMS 8606188 and ECS 8800281 is gratefully acknowledged.     

关于正整数奇偶分拆数的计算问题

正整数n的分拆是指将正整数n表示成一个或多个正整数的无序和,设O(n,m)表示将正整数n分拆成m个奇数之和的分拆数;e(n,m)表示将正整数n分拆成m个偶数之和的分拆数.本文用初等方法给出了将O(n,m),e(n,m)分别化为有限个O(n,2),e(n,2)的和的计算公式,进而达到计算O(n,m),e(n,m)的值.同时,还讨论了将正整数n分拆成互不相同的奇数或偶数的分拆数的相应的递推计算方法.     

偶一致超图划分问题的若干结果

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

Tribonacci partition formulas modulo m

Each Tribonacci sequence starting with an arbitrary triple of integers is periodic modulo m for any modulus m 〉 1. For a given m, the mapping between the set S of all m^3 triples of initial values and the set of their coresponding periods define a partition of the set S. In this paper we shall investigate some basic questions related to these partitions from the point of view of enumerative combinatorics.     

A new method for counting trees with vertex partition

A direct and elementary method is provided in this paper for counting trees with vertex partition instead of recursion, generating function, functional equation, Lagrange inversion, and matrix methods used before. This work was supported by the National Natural Science Foundation of China (Grant No. 10571013)     

B-splines on 3-D tetrahedron partition in four-directional mesh

It is more difficult to construct 3-D splines than in 2-D case. Some results in the three directional meshes of bivariate case have been extended to 3-D case and corresponding tetrahedron partition has been constructed. The support of related B-splines and their recurrent formulas on integration and differentiation-difference are obtained. The results of this paper can be extended into higher dimension spaces, and can be also used in wavelet analysis, because of the relationship between spline and wavelets.     

A remark on accessibility

This note obtains some characteristics of accessibility and Kato’s chaos. Applying these results, an accessible dynamical system whose product system is not accessible is constructed, giving a negative answer to a question in [Li R, Wang H, Zhao Y. Kato’s chaos in duopoly games. Chaos Solit Fract 2016;84:69–72]. Besides, it is proved that every transitive interval self-map is accessible.