A note on the asymptotic and computational complexity of graph distinguishability.
Displaying 21 – 40 of 430
A note on the critical group of a line graph.
Perkinson, David, Salter, Nick, Xu, Tianyuan (2011)
The Electronic Journal of Combinatorics [electronic only]
A numerical invariant for finitely generated groups via actions on graphs.
William L. Paschke (1993)
Mathematica Scandinavica
A spelling theorem for staggered generalized 2-complexes, with applications.
J. Howie, S.J. Pride (1984)
Inventiones mathematicae
About noncommuting graphs.
Moghaddamfar, Ali Reza (2006)
Sibirskij Matematicheskij Zhurnal
Addendum to : “Prime graph components of finite almost simple groups” [Rend. Sem. Mat. Univ. Padova 102 (1999), 1–22]
Maria Silvia Lucido (2002)
Rendiconti del Seminario Matematico della Università di Padova
Addendum to “Ring elements as sums of units”
Charles Lanski, Attila Maróti (2013)
Open Mathematics
We give a comment to Theorem 1.1 published in our paper “Ring elements as sums of units” [Cent. Eur. J. Math., 2009, 7(3), 395–399].
Algebraic tools for the construction of colored flows with boundary constraints
Marius Dorkenoo, Marie-Christine Eglin-Leclerc, Eric Rémila (2004)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We give a linear time algorithm which, given a simply connected figure of the plane divided into cells, whose boundary is crossed by some colored inputs and outputs, produces non-intersecting directed flow lines which match inputs and outputs according to the colors, in such a way that each edge of any cell is crossed by at most one line. The main tool is the notion of height function, previously introduced for tilings. It appears as an extension of the notion of potential of a flow in a planar...
Algebraic tools for the construction of colored flows with boundary constraints
Marius Dorkenoo, Marie-Christine Eglin-Leclerc, Eric Rémila (2010)
RAIRO - Theoretical Informatics and Applications
We give a linear time algorithm which, given a simply connected figure of the plane divided into cells, whose boundary is crossed by some colored inputs and outputs, produces non-intersecting directed flow lines which match inputs and outputs according to the colors, in such a way that each edge of any cell is crossed by at most one line. The main tool is the notion of height function, previously introduced for tilings. It appears as an extension of the notion of potential of a flow in...
Algorithms for Finding Unitals and Maximal Arcs in Projective Planes of Order 16
Stoichev, Stoicho (2007)
Serdica Journal of Computing
The paper has been presented at the International Conference Pioneers of Bulgarian Mathematics, Dedicated to Nikola Obreshkoff and Lubomir Tschakalo ff , Sofia, July, 2006.Two heuristic algorithms (M65 and M52) for finding respectively unitals and maximal arcs in projective planes of order 16 are described. The exact algorithms based on exhaustive search are impractical because of the combinatorial explosion (huge number of combinations to be checked). Algorithms M65 and M52 use unions of orbits...
Amalgamations and link graphs of Cayley graphs.
Tomanová, J. (1991)
Acta Mathematica Universitatis Comenianae. New Series
Amenability, unimodularity, and the spectral radius of random walks on finite graphs.
Wolfgang Woess, Paolo M. Soardi (1990)
Mathematische Zeitschrift
Amenable group actions on infinite graphs.
Wolfgang Woess (1989)
Mathematische Annalen
Amenable groups and cellular automata
Tullio G. Ceccherini-Silberstein, Antonio Machi, Fabio Scarabotti (1999)
Annales de l'institut Fourier
We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.
An application of Ramanujan graphs to C*-algebra tensor products, II
Alain Valette (1995/1996)
Séminaire de théorie spectrale et géométrie
An invariant for finitely presented ...G-modules.
William L. Paschke (1995)
Mathematische Annalen
Another way for associating a graph to a group
Alain Bretto, Alain Faisant (2005)
Mathematica Slovaca
Antisymmetric flows and strong colourings of oriented graphs
J. Nešetřill, André Raspaud (1999)
Annales de l'institut Fourier
The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number (as the modular version...
Applications of Topological Graph Theory for Group Theory.
Richard Z. Goldstein, E.C. Turner (1979)
Mathematische Zeitschrift
Arc-transitive and s-regular Cayley graphs of valency five on Abelian groups
Mehdi Alaeiyan (2006)
Discussiones Mathematicae Graph Theory
Let G be a finite group, and let . A Cayley di-graph Γ = Cay(G,S) of G relative to S is a di-graph with a vertex set G such that, for x,y ∈ G, the pair (x,y) is an arc if and only if . Further, if , then Γ is undirected. Γ is conected if and only if G = ⟨s⟩. A Cayley (di)graph Γ = Cay(G,S) is called normal if the right regular representation of G is a normal subgroup of the automorphism group of Γ. A graph Γ is said to be arc-transitive, if Aut(Γ) is transitive on an arc set. Also, a graph Γ...