Search

Funding: Peter J. Cameron acknowledges the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme Groups, representations and applications: new perspectives (supported by EPSRC grant no. EP/R014604/1), where he held a Simons Fellowship. For this research, T. Kavaskar was supported by the University Grant Commissions Start-Up Grant, Government of India grant No. F. 30-464/2019 (BSR) dated 27.03. T. Tamizh Chelvam was supported by CSIR Emeritus Scientist Scheme (No. 21 (1123)/20/EMR-II) of Council of Scientific and Industrial Research, Government of India. The zero-divisor graph of a finite commutative ring with unity is the graph whose vertex set is the set of zero-divisors in the ring, with a and b adjacent if ab=0. We show that the class of zero-divisor graphs is universal, in the sense that every finite graph is isomorphic to an induced subgraph of a zero-divisor graph. This remains true for various restricted classes of rings, including boolean rings, products of fields, and local rings. But in more restricted classes, the zero-divisor graphs do not form a universal family. For example, the zero-divisor graph of a local ring whose maximal ideal is principal is a threshold graph; and every threshold graph is embeddable in the zero-divisor graph of such a ring. More generally, we give necessary and sufficient conditions on a non-local ring for which its zero-divisor graph to be a threshold graph. In addition, we show that there is a countable local ring whose zero-divisor graph embeds the Rado graph , and hence every finite or countable graph, as induced subgraph. Finally, we consider embeddings in related graphs such as the 2-dimensional dot product graph. Publisher PDF

Infinite analogues of the Paley graphs are constructed, based on uncountably many infinite but locally finite fields. Weil's estimate for character sums shows that they are all isomorphic to the random or universal graph of Erd\H os, R\'enyi and Rado. Automorphism groups and connections with model theory are considered., Comment: 10 pages/

A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U . Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an induced universal graph with ( 1 + o ( 1 ) ) ⋅ 2 ( n − 1 ) ∕ 2 vertices improving the previous best bound of 16 ⋅ 2 n ∕ 2 by Alstrup et al. (2015) and matching the lower bound of 2 ( n − 1 ) ∕ 2 by Moon (1965) up to lower order additive terms. We continue this line of research of finding the size of the smallest induced universal graph up to lower order additive terms for some basic graph families. For the family of graphs with n vertices and bounded degree D = O ( 1 ) , Alon and Nenadov [Math. Proc. Camb. Philos. Soc. 2017] [4] showed that the smallest induced universal graph has size Θ n D ∕ 2 , but it remains to find the constant hidden in the O -notation. For even D the bound O n D ∕ 2 was already shown by Butler (2009). In order to find the correct constants for general D > 0 , it is natural first to consider the case D = 2 . For D = 2 , Butler gave an induced universal graph of size 6 . 5 n and subsequently, Esperet et al. (2008) found an induced universal graph for D = 2 of size 2 . 5 n . We construct for D = 2 an even smaller induced universal graph with 2 n − 1 vertices. This proves a conjecture by Esperet et al. stating the existence of such a graph with 2 n + o ( n ) vertices. For the family of acyclic graphs on n vertices with maximum degree 2 we show that the smallest induced universal graph has size 3 n 2 . We also introduce the notion of size oblivious and size aware decoding, and relate this to families of induced universal graphs. For the family of graphs consisting of a single cycle we prove new upper and lower bounds on the complexity of size aware and size oblivious decoders. These new bounds separate the two notions.

We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms., (v2): -Fixed some typos -Added more references

Motivated by the prevalent data science applications of processing and mining large-scale graph data such as social networks, web graphs, and biological networks, as well as the high I/O and communication costs of storing and transmitting such data, this paper investigates lossless compression of data appearing in the form of a labeled graph. A universal graph compression scheme is proposed, which does not depend on the underlying statistics/distribution of the graph model. For graphs generated by a stochastic block model, which is a widely used random graph model capturing the clustering effects in social networks, the proposed scheme achieves the optimal theoretical limit of lossless compression without the need to know edge probabilities, community labels, or the number of communities. The key ideas in establishing universality for stochastic block models include: 1) block decomposition of the adjacency matrix of the graph; 2) generalization of the Krichevsky-Trofimov probability assignment, which was initially designed for i.i.d. random processes. In four benchmark graph datasets (protein-to-protein interaction, LiveJournal friendship, Flickr, and YouTube), the compressed files from competing algorithms (including CSR, Ligra+, PNG image compressor, and Lempel-Ziv compressor for two-dimensional data) take 2.4 to 27 times the space needed by the proposed scheme.

A classic application of description length is for model selection with the minimum description length (MDL) principle. The focus of this paper is to extend description length for data analysis beyond simple model selection and sequences of scalars. More specifically, we extend the description length for data analysis in Gaussian graphical models. These are powerful tools to model interactions among variables in a sequence of i.i.d Gaussian data in the form of a graph. Our method uses universal graph coding methods to accurately account for model complexity, and therefore provide a more rigorous approach for graph model selection. The developed method is tested with synthetic and electrocardiogram (ECG) data to find the graph model and anomaly in Gaussian graphical models. The experiments show that our method gives better performance compared to commonly used methods., Comment: Submitted to ISIT 2021

It is well-known that the winning region of a parity game with $n$ nodes and $k$ priorities can be computed as a $k$-nested fixpoint of a suitable function; straightforward computation of this nested fixpoint requires $\mathcal{O}(n^{\frac{k}{2}})$ iterations of the function. Calude et al.'s recent quasipolynomial-time parity game solving algorithm essentially shows how to compute the same fixpoint in only quasipolynomially many iterations by reducing parity games to quasipolynomially sized safety games. Universal graphs have been used to modularize this transformation of parity games to equivalent safety games that are obtained by combining the original game with a universal graph. We show that this approach naturally generalizes to the computation of solutions of systems of \emph{any} fixpoint equations over finite lattices; hence, the solution of fixpoint equation systems can be computed by quasipolynomially many iterations of the equations. We present applications to modal fixpoint logics and games beyond relational semantics. For instance, the model checking problems for the energy $\mu$-calculus, finite latticed $\mu$-calculi, and the graded and the (two-valued) probabilistic $\mu$-calculus -- with numbers coded in binary -- can be solved via nested fixpoints of functions that differ substantially from the function for parity games but still can be computed in quasipolynomial time; our result hence implies that model checking for these $\mu$-calculi is in QP. Moreover, we improve the exponent in known exponential bounds on satisfiability checking., Comment: extended version of conference paper

A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that contains isometric copies of all $n$-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest., Comment: 13 pages, no figure. v2: revised version

Deep learning has been successful in many fields such as acoustics, image, and natural language processing. However, due to the unique characteristics of graphs, deep learning using universal graph data is not easy. The Graph Attention Networks (GATs) show the best performance in multiple authoritative node classification benchmark tests (including transductive and inductive). The purpose of this research is to design and implement an FPGA-based accelerator called S-GAT for graph attention networks that achieves excellent performance on acceleration and energy efficiency without losing accuracy, and does not rely on DSPs and large amounts of on-chip memory. We design S-GAT with software and hardware co-optimization. Specifically, we use model compression and feature quantization to reduce the model size, and use shift addition units (SAUs) to convert multiplication into shift operation to further reduce the computation requirements. We integrate the above optimizations into a universal hardware pipeline for various structures of GATs. At last, we evaluate our design on an Inspur F10A board with an Intel Arria 10 GX1150 and 16 GB DDR3 memory. Experimental results show that S-GAT can achieve 7.34 times speedup over Nvidia Tesla V100 and 593 times over Xeon CPU Gold 5115 while maintaining accuracy, and 48 times and 2400 times on energy efficiency respectively.

In the vast literature on waves and plasma interaction, the skin depth, the stochastic heating and the radiofrequency (rf) magnetic field effects emerge as important factors in simulations, still relying on effective collision rate models: a closed form and universal graph are given for stochastic heating. A simulation code based on iteration between plasma and rf calculations is recalled, and typical results are shown, for a simple induction ion source design.

International audience; We demonstrate that a large class of one-dimensional quantum and classical exchange models can be described by the same type of graphs, namely Cayley graphs of the permutation group. Their well-studied spectral properties allow us to derive crucial information about those models of fundamental importance in both classical and quantum physics, and to completely characterize their algebraic structure. Notably, we prove that the spectral gap can be obtained in polynomial computational time, which has strong implications in the context of adiabatic quantum computing with quantum spin-chains. This quantity also characterizes the rate to stationarity of some important classical random processes such as interchange and exclusion processes. Reciprocally, we use results derived from the celebrated Bethe ansatz to obtain original mathematical results about these graphs in the unweighted case. We also discuss extensions of this unifying framework to other systems, such as asymmetric exclusion processes -- a paradigmatic model in non-equilibrium physics, or the more exotic non-Hermitian quantum systems.

We suggest a combinatorial classification of metric filtrations of measure spaces; a complete invariant of such a filtration is its combinatorial scheme, a measure on the space of hierarchies of the group Z. In turn, the notion of a combinatorial scheme is a source of new metric invariants of automorphisms approximated by means of basic filtrations. We construct a universal graph with an adic structure such that every automorphism can be realized on its path space.

We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.

We study the local k-coloring of graphs.We prove that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3.We prove that it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8. A local k-coloring of a graph G is a function f:V(G){1,2,,k} such that for each SV(G), 2|S|3, there exist u,vS with |f(u)f(v)| at least the size of the subgraph induced by S. The local chromatic number of G is (G)=min{k:Ghas a localk-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8.

It is shown to be consistent with various values of b , d and 2 ℵ 1 that there is a universal graph on ω 1 . Moreover, it is also shown that it is consistent that there is a universal graph on ω 1 — in other words, a universal symmetric function from ω 1 2 to 2 — but no such function from ω 1 2 to ω. The method used relies on iterating well known reals, such as Miller and Laver reals, and alternating this with the PID forcing which adds no new reals. The last sections examine the question of set valued universal functions.

Let H={H1,,Hk} be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, |H|2,K1,3H,for any integer n0, every 2-connected H-free graph G of order at least n0 is supereulerian, i.e.,G has a spanning closed trail,then H{K1,3} contains an Ni,j,k or a path where Ni,j,k denotes the graph obtained by attaching three vertex-disjoint paths of lengths i,j,k0 to a triangle.As an application, we characterize all the forbidden triples H with K1,3H such that every 2-connected H-free graph is supereulerian. As a byproduct, we also characterize minimal 2-connected non-supereulerian claw-free graphs.

In Knor et al. (2016) authors conjectured that for a graph G , W min ( G ) is achieved for a χ ( G ) -coloring-induced orientation. They also proved the conjecture holds for bipartite graphs, complete graphs, prisms and Petersen graph. However, we find that there exists a graph G such that any minimum Wiener index orientation of G is not χ ( G ) -coloring-induced. This means the conjecture does not hold in general. Furthermore, we explore some graphs which do not satisfy the conjecture.

Let GA be a hereditary family of graphs and H a family of acyclically directed graphs. A graph G ( V , E ) is a GA-H reduced graph if it can be obtained from a graph GA ( V , D ) ∈ GA by deleting the edges of an edge subgraph H ( V , E ′ ) ∈ H . The present paper complements reference [9] by proving that the following properties are equivalent: Property 1: u → v ∈ E ′ implies N GA [ u ] ⊆ N GA [ v ] . Property 2: u → v ∈ E ′ and v — w ∉ E ∪ E ′ = D implies u — w ∉ E ∪ E ′ = D . This equivalence implies that most of the algorithms in the above reference apply to the GA-H reduced graphs where H is the family of transitive edge subgraphs of the closed neighborhoods containment graphs of the graphs in GA. We also describe a polynomial time algorithm for maximum weight independent set under the weaker condition that H ( V , E ′ ) is a locally transitive edge subgraph of the closed neighborhoods containment graph of GA ( V , D ) .

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs E , B and F and a projection p : E → B with fiber F (i.e. p − 1 x ≅ F for all x ∈ V ( B ) ) such that the preimage of any edge x y of B is trivial (i.e. p − 1 x y ≅ K 2 ⊠ F ). Here we develop a framework to study which subgraphs S of B have trivial preimages (i.e. p − 1 S ≅ S ⊠ F ) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.

It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ( H -cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to P n is H -cospectral to P n . Interestingly, there are others. This paper finds digraphs that are H -cospectral with the path graph P n and whose underlying graphs are nonisomorphic, when n is odd, and finds that such graphs do not exist when n is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.

A connected graph G = ( V , E ) with m edges is called universal antimagic if for each set B of m positive integers there is an bijective function f : E → B such that the function f ˜ : V → N defined at each vertex v as the sum of all labels of edges incident to v is injective. In this work we prove that several classes of graphs are universal antimagic. Among others, paths, cycles, split graphs, and any graph which contains the complete bipartite graph K 2 , n as a spanning subgraph.

The shift graph G S is defined on the space of infinite subsets of natural numbers by letting two sets be adjacent if one can be obtained from the other by removing its least element. We show that this graph is not a minimum among the graphs of the form G f defined on some Polish space X , where two distinct points are adjacent if one can be obtained from the other by a given Borel function f : X → X . This answers the primary outstanding question from [8] .

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)−1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.

We present a new method to construct a family of co-spectral graphs. Our method is based on a new type of graph product that we define, the bipartite graph product, which may be of self-interest. Our method is different from existing techniques in the sense that it is not based on a sequence of local graph operations (e.g. Godsil–McKay switching). The explicit nature of our construction allows us, for example, to construct an infinite family of cospectral graphs and provide an easy proof of non-isomorphism. We are also able to characterize fully the spectrum of the cospectral graphs.

Let d 1 , d 2 , … , d k be k non-negative integers. A graph G is ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , … , k . In this paper, we prove that every planar graph without cycles of length 4 or 9 is ( 1 , 1 , 0 ) -colorable.