Representation of finite graphs as difference graphs of S-units. I

DOI10.1016/J.JCTA.2014.07.001zbMATH Open1297.05168DBLPjournals/jct/GyoryHT14arXiv1408.5873OpenAlexW2470641761WikidataQ101186169 ScholiaQ101186169MaRDI QIDQ406579FDOQ406579

R. Tijdeman, Lajos Hajdu, Kálmán Győry

Publication date: 8 September 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let G be a simple finite graph such that each vertex has an integer value and different vertices have different values. Let S be a finite non-empty set of primes. We call G an S-graph if any two vertices are connected by an edge if and only their values differ by a number which is composed of primes from S. We prove e.g. that for every G there exist infinitely many finite sets S such that G is an S-graph. We deal with cycles and complete bipartite graphs G. We consider the triangles in G for a deeper analysis. Finally we prove that G is an S-graph for all S if and only if G is cubical. Besides combinatorial and numbertheoretical arguments some deep Diophantine results concerning S-unit equations are used in our proofs.

Full work available at URL: https://arxiv.org/abs/1408.5873

zbMATH Keywords

cubic graphsrepresentability\(S\)-unit equationsarithmetic graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• On the unitary Cayley graph of a finite ring
• A survey of the theory of hypercube graphs
• On equations in S-units and the Thue-Mahler equation
• On cycles in the sequence of unitary Cayley graphs
• Some properties of unitary Cayley graphs
• Ring elements as sums of units.
• Linear equations in variables which lie in a multiplicative group
• Representations of graphs and orthogonal latin square graphs
• On certain arithmetic graphs and their applications to diophantine problems
• On S-unit equations in two unknowns
• On the number of solutions of linear equations in units of an algebraic number field
• On cubical graphs
• Corrigendum to ``The complexity of cubical graphs
• A generalization of the unit and unitary Cayley graphs of a commutative ring
• Longest induced cycles in circulant graphs
• The difference graph of \(S\)-units
• On discriminants and indices of integers of an algebraic number field.
• On the irreducibility of a class of polynomials, IV
• $B$-valuations of graphs
• Irreducibility criteria of Schur-type and Pólya-type
• Small points on subvarieties of a torus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• On the smallest number of terms of vanishing sums of units in number fields
• On conjectures and problems of Ruzsa concerning difference graphs of \(S\)-units

This page was built for publication: Representation of finite graphs as difference graphs of \(S\)-units. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406579)