Factoring cartesian-product graphs

In a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge set E(G) of a connected graph G to decompose G into a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,” Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,” European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,” Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from finite to infinite graphs.     

Parallel permit grammars and some graph representations of Petri nets

The graph of a set grammar is introduced in such a way that each set rule of the grammar is represented by a cartesian subgraph of it. The correspondence between cartesian subgraphs and transitions of Petri nets (which satisfy the axiom of extensionality) is established. The set grammars with input (initial) and output (terminal) elements are studied in an analogy to Chomsky's string grammars and their strong equivalence. Permit rules and parallel permit rules are introduced in such a way that parallel permit grammars are more general tools than Petri nets themselves, because the equivalence between homogeneous parallel permit grammars and set grammars (and Petri nets) is proved.     

The vertex isoperimetric problem for the powers of the diamond graph

We introduce a new graph for all whose cartesian powers the vertex isoperimetric problem has nested solutions. This is the fourth kind of graphs with this property besides the well-studied graphs like hypercubes, grids, and tori. In contrast to the mentioned graphs, our graph is not bipartite. We present an exact solution to the vertex isoperimetric problem on our graph by introducing a new class of orders that unifies all known isoperimetric orders defined on the cartesian powers of graphs.     

Flows on graphs applied to diagonal similarity and diagonal equivalence for matrices

Three equivalence relations are considered on the set of n × n matrices with elements in F₀, an abelian group with absorbing zero adjoined. They are the relations of diagonal similarity, diagonal equivalence, and restricted diagonal equivalence. These relations are usually considered for matrices with elements in a field. But only multiplication is involved. Thus our formulation in terms of an abelian group with o is natural. Moreover, if F is chosen to be an additive group, diagonal similarity is characterized in terms of flows on the pattern graph of the matrices and diagonal equivalence in terms of flows on the bipartie graph of the matrices. For restricted diagonal equivalence a pseudo-diagonal of the graph must also be considered. When no pseudo-diagonal is present, the divisibility properties of the group F play a role. We show that the three relations are characterized by cyclic, polygonal, and pseudo-diagonal products for multiplicative F. Thus, our method of reducing propositions concerning the three equivalence relations to propositions concerning flows on graphs, provides a unified approach to problems previously considered independently, and yields some n, w or improved results. Our consideration of cycles rather than circuits eliminates certain restrictions (e.g., the complete reducibility of the matrices) which have previously been imposed. Our results extend theorems in Engel and Schneider [5], where however the group F is permitted to be non-commutative.     

三类笛卡尔积图的关联色数

图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。     

Regularity of the category of Kelley spaces

We show that the cartesian closed category of compactly generated Hausdorff spaces is regular, but is neither exact, nor locally cartesian closed. In fact we find a coequalizer of an equivalence relation which is not stable under pullback.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

A new constrained edit distance between quotiented ordered trees

In this paper we propose a dynamic programming algorithm to compare two quotiented ordered trees using a constrained edit distance. An ordered tree is a tree in which the left-to-right order among siblings is significant. A quotiented ordered tree is an ordered tree T with an equivalence relation on vertices and such that, when the equivalence classes are collapsed to super-nodes, the graph so obtained is an ordered tree as well. Based on an algorithm proposed by Zhang and Shasha [K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18 (6) (1989) 1245–1262] and introducing new notations, we describe a tree edit distance between quotiented ordered trees preserving equivalence relations on vertices during computation which works in polynomial time. Its application to RNA secondary structures comparison is finally presented.     

Two Ways to Centralizers of Equivalence Relations

We investigate what is the common part of the action accessible and the fibrewise algebraically cartesian closed (facc) categories dealing with the existence of centralizers of equivalence relations. Doing this, we shall introduce some new aspects of the Beck-Chevalley commutation with respect to the fibration of points \(\P _{\mathbb C}\) and shall characterize the existence of those centralizers by a specific property of this same fibration.     

Excess in critical graphs

In this paper we prove that the cartesian product of two trees is a semistable graph and we exhibit several vertices of semistability. We show that in most cases the cartesian product of two paths is completely semistable and we list the exceptions. Finally, we characterize stable composite graphs.     

The Maximality of Cartesian Categories

It is proved that equations between arrows assumed for cartesian categories are maximal in the sense that extending them with any new equation in the language of free cartesian categories collapses a cartesian category into a preorder. An analogous result holds for categories with binary products, which may lack a terminal object. The proof is based on a coherence result for cartesian categories, which is related to model‐theoretic methods of normalization. This maximality of cartesian categories, which is analogous to Post completeness, shows that the usual equivalence between deductions in conjunctive logic induced by βη normalization in natural deduction is chosen optimally.     

The Zero-Divisor Graph Associated to a Semigroup

The zero-divisor graph of a commutative semigroup with zero is the graph whose vertices are the nonzero zero-divisors of the semigroup, with two distinct vertices adjacent if the product of the corresponding elements is zero. New criteria to identify zero-divisor graphs are derived using both graph-theoretic and algebraic methods. We find the lowest bound on the number of edges necessary to guarantee a graph is a zero-divisor graph. In addition, the removal or addition of vertices to a zero-divisor graph is investigated by using equivalence relations and quotient sets. We also prove necessary and sufficient conditions for determining when regular graphs and complete graphs with more than two triangles attached are zero-divisor graphs. Lastly, we classify several graph structures that satisfy all known necessary conditions but are not zero-divisor graphs.     

Quasi-random classes of hypergraphs

We investigate the relations among a number of different graph properties for k-uniformhypergraphs, which are shared by random hypergraphs. Various graph properties form equivalence classes which in turn constitute a natural hierarchy. The analogues for binary functions on k-tuples and for hypergraphs with small density are also considered. Several classes are related to communication complexity and expander graphs.     

Infinite partitions of random graphs

We determine the set of canonical equivalence relations on [G]ⁿ, where G is a random graph, extending the result of Erd?s and Rado for the integers to random graphs.     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

Construction of minimal representative systems

A common algorithm for constructing a system of representatives for an equivalence relation is to extract minimal elements of equivalence classes with respect to some natural linear order. Methods for improving the efficiency of this process have been studied by Read [3]. In this paper we study these methods from a somewhat different point of view. We apply our methods to several basic classes of combinatorial objects and classical equivalence relations on these objects.     

Optimally pebbling hypercubes and powers

We point out that the optimal pebbling number of the n-cube is , and explain how to approximate the optimal pebbling number of the nth cartesian power of any graph in a similar way.     

Institutional Logics from the Aggregation of Organizational Networks: Operational Procedures for the Analysis of Counted Data

We address some problems of network aggregation that are central to organizational studies. We show that concepts of network equivalence (including generalizations and special cases of structural equivalence) are relevant to the modeling of the aggregation of social categories in cross-classification tables portraying relations within an organizational field (analogous to one-mode networks). We extend our results to model the dual aggregation of social identities and organizational practices (an example of a two-mode network). We present an algorithm to accomplish such dual aggregation. Within the formal and quantitative framework that we present, we emphasize a unified treatment of (a) aggregation on the basis of structural equivalence (invariance of actors within equivalence sets), (b) the study of variation in relations between structurally equivalent sets, and (c) the close connections between aggregation within organizational networks and multi-dimensional modeling of organizational fields.     

A local prime factor decomposition algorithm

This work is concerned with the prime factor decomposition (PFD) of strong product graphs. A new quasi-linear time algorithm for the PFD with respect to the strong product for arbitrary, finite, connected, undirected graphs is derived.Moreover, since most graphs are prime although they can have a product-like structure, also known as approximate graph products, the practical application of the well-known “classical” prime factorization algorithm is strictly limited. This new PFD algorithm is based on a local approach that covers a graph by small factorizable subgraphs and then utilizes this information to derive the global factors. Therefore, we can take advantage of this approach and derive in addition a method for the recognition of approximate graph products.     

Local Algorithms for the Prime Factorization of Strong Product Graphs

The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data. A first step towards error-tolerant “approximate” prime factorization, is the development of local approaches that cover the graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product. To this end we introduce the backbone \mathbbB (G)\mathbb{B} (G) for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors.