Star partitions on graphs

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.     

Fuzzy cardinality and the modeling of imprecise quantification

The concept of cardinality of a fuzzy set has received attention from several researchers and has been defined in several apparently independent manners. A systematic investigation of this notion is performed which unifies and improves previous attempts. The cardinality of a fuzzy set, viewed as a fuzzy integer, is related to scalar cardinality indices. The closely related question of the probability of a fuzzy event is dealt with. Lastly, the usefulness of fuzzy cardinality for meaning representation of statements or queries involving fuzzy linguistic quantifiers is emphasized.     

Characterizations of postman sets

Using results by McKee and Woodall on binary matroids, we show that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decomposition of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets.     

Cardinality enrichment of flexible cross correlation (FCC) code for SAC-OCDMA system by alleviation interference scheme (AIS)

In this paper, we propose an alleviation interference scheme (AIS) for spectral amplitude coding (SAC) – optical code division multiple access (OCDMA) coding system approaches. The AIS SAC-OCDMA systems is demonstrated by utilizing the new flexible cross correlation (FCC) code. The FCC code has advantages, such as flexibility in-phase cross-correlation at any given number of users and weights, as well as effectively reduces the impacts of phase-induced intensity noise (PIIN) and has the multiple-access interference (MAI) cancelation property. The results indicated good performance whereas the FCC (W = 4, K = 150) AIS SAC-OCDMA coding system offers 66%, 172%, 650% and 900% percentage of cardinality enrichments as a contrast to DCS (W = 4, K = 90), MDW (W = 4, K = 55), MFH (W = 4, K = 20) and Hadamard (W = 8, K = 15) codes, respectively. Finally, the FCC AIS SAC-OCDMA coding system has low effective receive power Psr = −21 dBm which is expected to be more significant for future SAC-OCDMA coding systems without requiring any amplification at the receiving plant.     

A continuous variable representation of the traveling salesman problem

The classic traveling salesman problem is characterized in terms of continuous flows on a specially constructed non-conservative network, in 2n – 1 linear constraints and a cardinality constraint. It is shown that every solution to the network problem is a hamiltonian circuit.     

Count of primitive words

Abstract. The present paper concerns with the formula of the count of primitive words and ex-changeable primitive words.     

关于(0,1)矩阵类U(R,S)的基数的一个猜测

在文献[1]中,魏万迪得到了(0,1)矩阵类U(R.S)的基数的一个下界。万宏辉在文献[2]中给出了|U(R.S)|达到这个下界的一个充分条件,他并且猜测这个充分条件也是必要的。在本文中,我们将证明万的猜测为真,从而得到基数|U(R,S)|达到魏万迪下界的一个充分必要条件.