Search

In this paper, after recalling the main properties of the voice transform, we prove its inversion formula, then we present some qualitative uncertainty principles associated with this transform. Finally, we find a solution to an interpolation problem. [ABSTRACT FROM AUTHOR]

We characterise the slices of the category of graphs that are algebraically universal in terms of the structure of the slicing graph. In particular, we show that algebraic universality is obtained if, and only if, the slicing graph contains one of four fixed graphs as a subgraph. [ABSTRACT FROM AUTHOR]

For a hereditary family of graphs F , let F n denote the set of all members of F on n vertices. The speed of F is the function f (n) = | F n | . An implicit representation of size ℓ (n) for F n is a function assigning a label of ℓ (n) bits to each vertex of any given graph G ∈ F n , so that the adjacency between any pair of vertices can be determined by their labels. Bonamy, Esperet, Groenland, and Scott proved that the minimum possible size of an implicit representation of F n for any hereditary family F with speed 2 Ω (n 2) is (1 + o (1)) log 2 | F n | / n ( = Θ (n) ). A recent result of Hatami and Hatami shows that the situation is very different for very sparse hereditary families. They showed that for every δ > 0 there are hereditary families of graphs with speed 2 O (n log n) that do not admit implicit representations of size smaller than n 1 / 2 - δ . In this note we show that even a mild speed bound ensures an implicit representation of size O (n c) for some c < 1 . Specifically we prove that for every ε > 0 there is an integer d ≥ 1 so that if F is a hereditary family with speed f (n) ≤ 2 (1 / 4 - ε) n 2 then F n admits an implicit representation of size O (n 1 - 1 / d log n) . Moreover, for every integer d > 1 there is a hereditary family for which this is tight up to the logarithmic factor. [ABSTRACT FROM AUTHOR]

In this paper, we study Dirac-type theorems for an inhomogenous random graph G whose edge probabilities are not necessarily all the same. We obtain sufficient conditions for the existence of Hamiltonian paths and perfect matchings, in terms of the sum of edge probabilities. For edge probability assignments with two-sided bounds, we use Pósa rotation and single vertex exclusion techniques to show that G is Hamiltonian with high probability. For weaker one-sided bounds, we use bootstrapping techniques to obtain a perfect matching in G , with high probability. We also highlight an application of our results in the context of channel assignment problem in wireless networks. [ABSTRACT FROM AUTHOR]

We prove that the stack-number of the strong product of three n-vertex paths is Θ (n 1 / 3) . The best previously known upper bound was O(n). No non-trivial lower bound was known. This is the first explicit example of a graph family with bounded maximum degree and unbounded stack-number. The main tool used in our proof of the lower bound is the topological overlap theorem of Gromov. We actually prove a stronger result in terms of so-called triangulations of Cartesian products. We conclude that triangulations of three-dimensional Cartesian products of any sufficiently large connected graphs have large stack-number. The upper bound is a special case of a more general construction based on families of permutations derived from Hadamard matrices. The strong product of three paths is also the first example of a bounded degree graph with bounded queue-number and unbounded stack-number. A natural question that follows from our result is to determine the smallest Δ 0 such that there exists a graph family with unbounded stack-number, bounded queue-number and maximum degree Δ 0 . We show that Δ 0 ∈ { 6 , 7 } . [ABSTRACT FROM AUTHOR]

We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in R 3 . We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K 5 , K 5 , 81 , or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K 4 , 4 , and K 3 , 5 can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (Isr. J. Math. 46(1–2), 127–144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω (n log n) . From the non-realizability of K 5 , 81 , we obtain that any realizable n-vertex graph has O (n 9 / 5) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense. [ABSTRACT FROM AUTHOR]

In this paper, we study "robust" dominating sets of random graphs that retain the domination property even if a small deterministic set of edges are removed. We motivate our study by illustrating with examples from wireless networks in harsh environments. We then use the probabilistic method and martingale difference techniques to determine sufficient conditions for the asymptotic optimality of the robust domination number. We also discuss robust domination in sparse random graphs where the number of edges grows at most linearly in the number of vertices. [ABSTRACT FROM AUTHOR]

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson in his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee, and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still unknown. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4. [ABSTRACT FROM AUTHOR]

Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit 1-dimensional annular separators: The vertices at graph distance R from any vertex can be separated from those at distance 2R by removing at most O(R) vertices. They asked whether geometric d-dimensional graphs with uniform polynomial volume growth similarly admit (d - 1) -dimensional annular separators when d > 2 . We show that this fails in a strong sense: For any d ⩾ 3 and every s ⩾ 1 , there is a collection of interior-disjoint spheres in R d whose tangency graph G has uniform polynomial growth, but such that all annular separators in G have cardinality at least R s . [ABSTRACT FROM AUTHOR]

A sequence σ of p non-negative integers is unigraphic if it is the degree sequence of exactly one graph, up to isomorphism. A polyhedral graph is a 3-connected, planar graph. We investigate which sequences are unigraphic with respect to the class of polyhedral graphs, meaning that they admit exactly one realisation as a polyhedron. We focus on the case of sequences with largest entry p - 2 . We give a classification of polyhedral unigraphic sequences starting with p - 2 , p - 2 , as well as those starting with p - 2 and containing exactly one 3. Moreover, we characterise the unigraphic sequences where a few vertices are of high degree. We conclude with a few other examples of families of unigraphic polyhedra. [ABSTRACT FROM AUTHOR]

Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that functionality is bounded for box intersection graphs in R 1 , i.e. for interval graphs, and unbounded for box intersection graphs in R 3 . We also study a parameter known as symmetric difference, which is intermediate between twin-width and functionality, and show that this parameter is unbounded both for interval graphs and for unit box intersection graphs in R 2 . [ABSTRACT FROM AUTHOR]

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains Ω (n 1 2) pairwise disjoint edges and a plane cycle (and hence path) of length Ω (log n log log n) . Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D. [ABSTRACT FROM AUTHOR]

A graph is called 1-planar if it can be drawn on the plane (or on the sphere) such that each edge is crossed at most once. It is known that a 1-planar graph G with at least three vertices has at most 4 | V (G) | - 8 edges, so G is optimal if G has exactly 4 | V (G) | - 8 edges. The vertex-connectivity of an optimal 1-planar graph has been proven to be either 4 or 6. According to the Whitney inequality, the edge-connectivity of an optimal 1-planar graph is at least 4. In this paper, we provide a more precise result. We prove that the edge-connectivity of every optimal 1-planar graph is 6. Additionally, we prove that any minimum edge-cut of an optimal 1-planar graph is a set of all the edges incident with a vertex of degree 6. In addition, we prove that an optimal 1-planar graph has the restricted edge-connectivity 8, 10 or 12. [ABSTRACT FROM AUTHOR]

In this paper, we consider the limit C ∗ -algebra induced by a chain of connected finite directed graphs, and study the free probability on it. In particular, we are interested in semicircular elements in the limit C ∗ -algebra whose free distributions are the semicircular law. Our main results not only characterize free-distributional data on the limit C ∗ -algebra, but also provide a natural way to study free probabilities on “infinite” graphs. [ABSTRACT FROM AUTHOR]

A grounded L-graph is the intersection graph of a collection of "L" shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number ω has chromatic number at most 17 ω 4 . This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially χ -bounded. We also survey χ -boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds. [ABSTRACT FROM AUTHOR]

ABSTRACTThe crossing number of a graph G in a surface Σ, denoted by [Formula: see text], is the minimum number of pairwise intersections of edges in a drawing of G in Σ. Let k be an integer satisfying [Formula: see text], the generalized Petersen graph [Formula: see text] is the graph with vertex set [Formula: see text] and edge set [Formula: see text] the subscripts are read modulo [Formula: see text] In this paper we investigate the crossing number of [Formula: see text] in the projective plane. We determine the exact value of [Formula: see text] is k–2 when [Formula: see text] moreover, for [Formula: see text] we get that [Formula: see text]

AbstractMax-point-tolerance graphs (MPTG) were introduced by Catanzaro et al. in 2017 as a generalization of interval graphs. This graph class has many practical applications in the study of the human genome as well as in signal processing for networks. The same class of graphs was also studied by Soto and Caro in 2015 with a different name, p -BOX(1) graphs. In our article, we consider a natural subclass of max-point-tolerance graphs, namely, proper max-point-tolerance graphs (proper MPTG), where intervals associated with the vertices are not contained in each other properly. We present the first characterization theorem of this graph class by defining certain linear ordering on the vertex set. In the course of this study, we prove proper max-point-tolerance graphs are asteroidal triple-free, and perfect. We also find that proper max-point-tolerance graphs are equivalent to unit max-point-tolerance graphs. Further, we show that MPTG (proper MPTG) and max-tolerance graphs (proper max-tolerance graphs) are incomparable. In conclusion, we demonstrate relations between proper MPTG with other variants of MPTG and max-tolerance graphs.

The metric representation of a vertex u in a connected graph G respect to an ordered vertex subset W = { ω 1 , ⋯ , ω n } ⊂ V (G) is the vector of distances r (u | W) = (d (u , ω 1) , ⋯ , d (u , ω n)) . A vertex subset W is a resolving set of G if r (u | W) ≠ r (v | W) , for every u , v ∈ V (G) with u ≠ v . Thus, a resolving set with n elements provides a set of metric representation vectors S ⊂ Z n with cardinal equal to the order of the graph. In this paper, we address the reverse point of view; that is, we characterize the finite subsets S ⊂ Z n that are realizable as the set of metric representation vectors of a graph G with respect to some resolving set W. We also explore the role that the strong product of paths plays in this context. Moreover, in the case n = 2 , we characterize the sets S ⊂ Z 2 that are uniquely realizable as the set of metric representation vectors of a graph G with respect to a resolving set W. [ABSTRACT FROM AUTHOR]

We show that there are O (n · 4 n / 11) planar graphs on n vertices which do not admit a simultaneous straight-line embedding on any n-point set in the plane. In particular, this improves the best known bound O(n!) significantly. [ABSTRACT FROM AUTHOR]

A rectangle visibility graph (RVG) is represented by assigning to each vertex a rectangle in the plane with horizontal and vertical sides in such a way that edges in the graph correspond to unobstructed horizontal and vertical lines of sight between their corresponding rectangles. To discretize, we consider only rectangles whose corners have integer coordinates. For any given RVG, we seek a representation with smallest bounding box as measured by its area, perimeter, height, or width (height is assumed not to exceed width). We derive a number of results regarding these parameters. Using these results, we show that these four measures are distinct, in the sense that there exist graphs G 1 and G 2 with area (G 1) < area (G 2) but perim (G 2) < perim (G 1) , and analogously for all other pairs of these parameters. We further show that there exists a graph G 3 with representations S 1 and S 2 such that area (G 3) = area (S 1) < area (S 2) but perim (G 3) = perim (S 2) < perim (S 1) . In other words, G 3 requires distinct representations to minimize area and perimeter. Similarly, such graphs exist to demonstrate the independence of all other pairs of these parameters. Among graphs with n ≤ 6 vertices, the empty graph E n requires largest area. But for graphs with n = 7 and n = 8 vertices, we show that the complete graphs K 7 and K 8 require larger area than E 7 and E 8 , respectively. Using this, we show that for all n ≥ 8 , the empty graph E n does not have largest area, perimeter, height, or width among all RVGs on n vertices. [ABSTRACT FROM AUTHOR]

Let K be a field, [ n ] = { 1 , ... , n } and H = ([ n ] , E) be a hypergraph. For an integer d ≥ 1 the Lovász-Saks-Schrijver ideal (LSS-ideal) L H K (d) ⊆ K [ y i j : (i , j) ∈ [ n ] × [ d ] ] is the ideal generated by the polynomials f e (d) = ∑ j = 1 d ∏ i ∈ e y i j for edges e of H. In this paper for an algebraically closed field K and a k-uniform hypergraph H = ([ n ] , E) we employ a connection between LSS-ideals and coordinate sections of the closure of the set S n , k d of homogeneous degree k symmetric tensors in n variables of rank ≤ d to derive results on the irreducibility of its coordinate sections. To this end we provide results on primality and the complete intersection property of L H K (d) . We then use the combinatorial concept of positive matching decomposition of a hypergraph H to provide bounds on when L H K (d) turns prime to provide results on the irreducibility of coordinate sections of S n , k d . [ABSTRACT FROM AUTHOR]

We introduce k-maximal sub-polygon graphs (k-MSP graphs), the intersection graphs of maximal polygons contained in a polygon with sides parallel to a regular 2k-gon. We prove that all complete graphs are k-MSP graphs for all k > 1 ; trees are 2-MSP graphs; trees are k-MSP graphs for k > 2 if and only if they are caterpillars; and n-cycles are not k-MSP graphs for n > 3 and k > 1 . We derive bounds for which j-cycles appear as induced subgraphs of k-MSP graphs. As our main result, we construct examples of graphs which are k-MSP graphs and not j-MSP graphs for all k > 1 , j > 1 , k ≠ j . [ABSTRACT FROM AUTHOR]

Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be N P -hard, which settles an open question. [ABSTRACT FROM AUTHOR]

There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs.

We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the edges of a random graph by cliques, Combinatorica 15 (1995) 489–497] and Guo, Patten, Warnke [Prague dimension of random graphs, manuscript submitted for publication].

We extend recent results of Abdo Alfakih, who constructed Colin de Verdière matrices for complements of penny graphs from Euclidean distance matrices, by interpreting them using the sphere representations of Kotlov, Lovász, and Vempala. Our results apply to complements of contact graphs of unit spheres in arbitrary dimension. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce the notion of intersection graphs based on non-trivial hyperideals in general hyperrings. In order to realise the article's goals, we design general hyperrings on any given ring and compute the set of all hyperideals of related general hyperring. Moreover to establish of connection between of hyperideals as vertices of it's associated graph, we introduce the concept of absorbing elements. The main method in this research is based on nonempty intersection of hyperideals, so we discuss on divisor of order of general hyperrings. As a result of the research, is constructing of some necessary and sufficient conditions in intersection graphs to be a connected(complete, Hamiltonian, or Eulerian) graph. Also, is presented notations of annihilator and kernel of homomorphisms via absorbing elements and fundamental relations. The paper includes implications for the development of intersection graph, for modelling the complex hypernetworks by absorbing elements, prime divisors and their relations in hyperideals. The new conception of intersection graphs based on hyperideals of general hyperrings was broached for the in this paper first time. [ABSTRACT FROM AUTHOR]

The Feferman–Vaught theorem provides a way of evaluating a first order sentence φ on a disjoint union of structures by producing a decomposition of φ into sentences which can be evaluated on the individual structures and the results of these evaluations combined using a propositional formula. This decomposition can in general be non-elementarily larger than φ . We introduce a "tree" generalization of the prenex normal form (PNF) for first order sentences, and show that for an input sentence in this form having a fixed number of quantifier alternations, a Feferman–Vaught decomposition can be obtained in time elementary in the size of the sentence. The sentences in the decomposition are also in tree PNF, and further have the same number of quantifier alternations and the same quantifier rank as the input sentence. We extend this result by considering binary operations other than disjoint union, in particular sum-like operations such as join, ordered sum and NLC-sum, that are definable using quantifier-free translation schemes. [ABSTRACT FROM AUTHOR]

We investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for (2 , 2) -tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of the torus we identify all 116 irreducible base graphs and provide a geometric application involving contact graphs of configurations of circular arcs. [ABSTRACT FROM AUTHOR]

The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs.

Thomassen described all (except finitely many) regular tilings of the torus S1 and the Klein bottle N2 into (3,6)-tilings, (4,4)-tilings and (6,3)-tilings. Many researchers made great e orts to investigate the crossing number of the Cartesian product of an m-cycle and an n-cycle, which is a special kind of (4,4)-tilings, either in the plane or in the projective plane. In this paper we study the crossing number of the hexagonal graph H3,n (n ≥ 2), which is a special kind of (3,6)-tilings, in the projective plane, and prove that crN1(H3,n)={0,n=2,n-1,n≥3.cr{N_1}\left( {{H_{3,n}}} \right) = \left\{ {\matrix{{0,} \hfill & {n = 2,} \hfill \cr {n - 1,} \hfill & {n \ge 3.} \hfill \cr } } \right.