Search

Let G be a simple graph of order $$n\ge 2$$ and let $$k\in \{1,\ldots ,n-1\}$$ . The k-token graph $$F_k(G)$$ of G is the graph whose vertices are the k-subsets of V(G), where two vertices are adjacent in $$F_k(G)$$ whenever their symmetric difference is an edge of G. In 2018 Leanos and Trujillo-Negrete proved that if G is t-connected and $$t\ge k$$ , then $$F_k(G)$$ is at least $$k(t-k+1)$$ -connected. In this paper we show that such a lower bound remains true in the context of edge-connectivity. Specifically, we show that if G is t-edge-connected and $$t\ge k$$ , then $$F_k(G)$$ is at least $$k(t-k+1)$$ -edge-connected. We also provide some families of graphs attaining this bound.

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial $$B(G;x):={\sum}_{k=-n}^{\partial(G)}B_k(G)x^{n+k}$$ , where Bk(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G; x) and its coefficients. In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G.

Let { p 1 , … , p n } and { q 1 , … , q n } be two sets of n labeled points in general position in the plane. We say that these two point sets have the same order type if for every triple of indices ( i , j , k ) , p k is above the directed line from p i to p j if and only if q k is above the directed line from q i to q j . In this paper we give the first non-trivial lower bounds on the number of different order types of n points that can be realized in integer grids of polynomial size.

Let G be a simple graph of order n and let $$k\in \{1,\ldots ,n-1\}$$ . The k-token graph $$F_k(G)$$ of G is the graph whose vertices are the k-subsets of V(G), where two vertices are adjacent in $$F_k(G)$$ whenever their symmetric difference is an edge of G. In 2012 Fabila et al. conjectured that if G is t-connected and $$t\ge k$$ , then $$F_k(G)$$ is $$k(t-k+1)$$ -connected. In this paper we prove this conjecture.

Let P be a set of n≥3 points in general position in the plane. The edge disjointness graph D(P) of P is the graph whose vertices are the n2 closed straight line segments with endpoints in P, two of which are adjacent in D(P) if and only if they are disjoint. In this paper we show that the connectivity of D(P) is at most 7n218+Θ(n), and that this upper bound is asymptotically tight. The proof is based on the analysis of the connectivity of D(Qn), where Qn denotes an n-point set that is almost 3-symmetric.

A plane drawing of a graph is cylindrical if there exist two concentric circles that contain all the vertices of the graph, and no edge intersects (other than at its endpoints) any of these circles. The cylindrical crossing number of a graph \(G\) is the minimum number of crossings in a cylindrical drawing of \(G\). In his influential survey on the variants of the definition of the crossing number of a graph, Schaefer lists the complexity of computing the cylindrical crossing number of a graph as an open question. In this paper, we prove that the problem of deciding whether a given graph admits a cylindrical embedding is NP-complete, and as a consequence we show that the \(t\)-cylindrical crossing number problem is also NP-complete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number, namely the \(t\)-crossing number.

Dirac in Shuster sta leta 1954 predstavila enostaven dokaz izreka Kuratowskega, ko sta pokazala, da poljubna 1-križno-kritična povezava grafa ?$G$? pripada neki subdiviziji Kuratowskega grafa ?$G$?. Leta 1983 je Širáň razširil ta rezultat na poljubno tako 2-križnokritično povezavo ?$e$? s krajiščema ?$b$? in ?$c$? v grafu ?$G$? s križnim številom najmanj dve, da nobena dva bloka grafa ?$G-b-c$? ne vsebujeta vseh njegovih vozlišč. Povezavo ?$f$? grafa ?$G$? je imenoval ?$k$?-izjemna, če je ?$f$? ?$k$?-križno-kritična in ne pripada nobenemu podgrafu Kuratowskega grafa ?$G$?. Nato je pokazal, da enostavni 3-povezani grafi s ?$k$?-izjemnimi povezavami obstajajo za poljuben ?$k \ge 6$? in da obstajajo celo za poljubno velike razlike ?${\rm cr}(G) - {\rm cr}(G - f)$?. Leta 1991 je Kochol konstruiral takšne primere za poljubne ?$k \ge 4$? in pripomnil, da Širáňov rezultat velja za poljuben enostaven graf. V pričujočem članku raziščemo primer, ko dva bloka vsebujeta vsa vozlišča grafa ?$G-b-c$?, in pokažemo, da grafi s ?$k$?-izjemnimi povezavami obstajajo za poljuben ?$k \ge 2$?, vendar niso nujno enostavni. Potrdimo, da ne obstajajo nobeni takšni enostavni grafi z 2-izjemnimi povezavami, in to z uporabo tehnik iz nedavne karakterizacije 2-križno-kritičnih grafov. Eksplicitno opišemo množico vseh grafov z 2-izjemnimi povezavami in opazimo, da vsi vsebujejo vzporedne povezave. V tem kontekstu je mogoče ta članek brati kot preludij h karakterizaciji 2-križno-kritičnih grafov.

Richter and Thomassen proved that every graph has an edge e such that the crossing number crG-e of G-e is at least 2/5crG-O1. Fox and Cs. Toth proved that dense graphs have large sets of edges proportional in the total number of edges whose removal leaves a graph with crossing number proportional to the crossing number of the original graph; this result was later strenghthened by Cerný, Kyncl, and G. Toth. These results make our understanding of the decay of crossing numbers in dense graphs essentially complete. In this article we prove a similar result for large sparse graphs in which the number of edges is not artificially inflated by operations such as edge subdivisions. We also discuss the connection between the decay of crossing numbers and expected crossing numbers, a concept recently introduced by Mohar and Tamon.

Let G = ( V , E ) be a simple graph with vertex set V and edge set E. Let D be a subset of V, and let B ( D ) be the set of neighbours of D in V ∖ D . The differential ∂ ( D ) of D is defined as | B ( D ) | − | D | . The maximum value of ∂ ( D ) taken over all subsets D ⊆ V is the differential ∂ ( G ) of G. For β ∈ ( − 1 , Δ ) , the β-differential ∂ β ( G ) of G is the maximum value of { | B ( D ) | − β | D | : D ⊆ V } . Motivated by an influential maximization problem, in this paper we study the β -differential of G.

Neil Sloane showed that the problem of determine the maximum size of a binary code of constant weight 2 that can correct a single adjacent transposition is equivalent to finding the packing number of a certain graph. In this paper we solve this open problem by finding the packing number of the double vertex graph (2-token graph) of a path graph. This double vertex graph is isomorphic to the Sloane's graph. Our solution implies a conjecture of Rob Pratt about the ordinary generating function of sequence A085680., Comment: 21 pages, 7 figures. V2: 22 pages, more figures added. V3. minor corrections based on referee's comments. One figure corrected. The title "On an error correcting code problem" has been changed

Consider a graph G with a minimal edge cut F and let G"1, G"2 be the two (augmented) components of G-F. A long-open question asks under which conditions the crossing number of G is (greater than or) equal to the sum of the crossing numbers of G"1 and G"2-which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|@?{0,1,2} and that there exist graphs violating this property with |F|>=4. In this paper, we show that crossing number is additive for |F|=3, thus closing the final gap in the question. The techniques generalize to show that minor crossing number is additive over edge cuts of arbitrary size, as well as to provide bounds for crossing number additivity in arbitrary surfaces. We point out several applications to exact crossing number computation and crossing-critical graphs, as well as provide a very general lower bound for the minor crossing number of the Cartesian product of an arbitrary graph with a tree.

Let P be a set of points in general position in the plane. Join all pairs of points in P with straight line segments. The number of segment-crossings in such a drawing, denoted by $\operatorname {cr}(P)$, is the rectilinear crossing number of P. A halving line of P is a line passing through two points of P that divides the rest of the points of P in (almost) half. The number of halving lines of P is denoted by h(P). Similarly, a k-edge, 0≤k≤n/2−1, is a line passing through two points of P and leaving exactly k points of P on one side. The number of ≤k-edges of P is denoted by E ≤k (P). Let $\overline {\mathrm {cr}}(n)$, h(n), and E ≤k (n) denote the minimum of $\operatorname {cr}(P)$, the maximum of h(P), and the minimum of E ≤k (P), respectively, over all sets P of n points in general position in the plane. We show that the previously best known lower bound on E ≤k (n) is tight for k

There are two properties shared by all known crossing-minimizing geometric drawings of K"n, for n a multiple of 3. First, the underlying n-point set of these drawings minimizes the number of (@?k)-edges, that means, has exactly 3(k+22)(@?k)-edges, for all 0@?k

Even the most superficial glance at the vast majority of crossing-minimal geometric drawings of K"n reveals two hard-to-miss features. First, all such drawings appear to be 3-fold symmetric (or simply 3-symmetric). And second, they all are 3-decomposable, that is, there is a triangle T enclosing the drawing, and a balanced partition A,B,C of the underlying set of points P, such that the orthogonal projections of P onto the sides of T show A between B and C on one side, B between A and C on another side, and C between A and B on the third side. In fact, we conjecture that all optimal drawings are 3-decomposable, and that there are 3-symmetric optimal constructions for all n multiples of 3. In this paper, we show that any 3-decomposable geometric drawing of K"n has at least 0.380029(n4)[email protected](n^3) crossings. On the other hand, we produce 3-symmetric and 3-decomposable drawings that improve the general upper bound for the rectilinear crossing number of K"n to 0.380488(n4)[email protected](n^3). We also give explicit 3-symmetric and 3-decomposable constructions for n

We describe a relationship between the crossing number of a graph G with a 2-edge-cut C and the crossing numbers of the components of G-C. Let G be a connected graph with a 2-edge-cut C := [V1,V2]. Let u1u2, v1v2 be the edges of C, so that ui,vi ∈ Vi for i = 1,2, and let Gi := G[Vi] and G'i := Gi + uivi. We show that if either G1 or G2 is not connected, then cr (G) = cr (G1) + cr (G2), and that if they are both connected then cr (G) = cr (G'1) + cr (G'2). We use this to show how to decompose crossing-critical graphs with 2-edge-cuts into smaller, 3-edge-connected crossing-critical graphs. We also observe that this settles a question arising from knot theory, raised by Sawollek, by describing exactly under which conditions the crossing number of the connected sum of two graphs equals the sum of the crossing numbers of the individual graphs.

For n ⩽ 27 we present exact values for the maximum number h ( n ) of halving lines and h ˜ ( n ) of halving pseudolines, determined by n points in the plane. For this range of values of n we also present exact values of the rectilinear c r ¯ ( K n ) and the pseudolinear c r ˜ ( K n ) crossing numbers of the complete graph K n . h ˜ ( n ) and c r ˜ ( K n ) are new for n ∈ { 14 , 16 , 18 , 20 , 22 , 23 , 24 , 25 , 26 , 27 } , h ( n ) is new for n ∈ { 16 , 18 , 20 , 22 , 23 , 24 , 25 , 26 , 27 } , and c r ¯ ( K n ) is new for n ∈ { 20 , 22 , 23 , 24 , 25 , 26 , 27 } .

A generalized configuration is a set of n points and ( n 2 ) pseudolines such that each pseudoline passes through exactly two points, two pseudolines intersect exactly once, and no three pseudolines are concurrent. Following the approach of allowable sequences we prove a recursive inequality for the number of (⩽ k )-sets for generalized configurations. As a consequence we improve the previously best known lower bound on the pseudolinear and rectilinear crossing numbers from 0.37968 ( n 4 ) + Θ ( n 3 ) to 0.379972 ( n 4 ) + Θ ( n 3 ) .

It is shown that if a simple Euclidean arrangement of n pseudolines has no (≥ 5)-gons, then it has exactly n - 2 triangles and (n - 2)(n - 3)/2 quadrilaterals. We also describe how to construct all such arrangements, and as a consequence we show that they are all stretchable.

We show that for each integer g 0 there is a constant cg > 0 such that every graph that embeds in the projective plane with sucien tly large face{width r has crossing number at least cgr 2 in the orientable surface g of genus g. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.

Let $G=(V,E)$ be a graph of order $n$ and let $1\leq k< n$ be an integer. The $k$-token graph of $G$ is the graph whose vertices are all the $k$-subsets of $V$, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper we characterize precisely, for each value of $k$, which graphs have a regular $k$-token graph and which connected graphs have a planar $k$-token graph., 13 pages, 5 figures. Referee suggestions and corrections incorporated (in particular, a mistake in the proof of Theorem 2.9 was fixed). One reference added. Accepted for publication in "Discussiones Mathematicae Graph Theory"

Devadoss asked: (1) can every polygon be convexified so that no internal visibility (between vertices) is lost in the process? Moreover, (2) does such a convexification exist, in which exactly one vertex is moved at a time (that is, using {\em single-vertex moves})? We prove the redundancy of the "single-vertex moves" condition: an affirmative answer to (1) implies an affirmative answer to (2). Since Aichholzer et al. recently proved (1), this settles (2).

Combinatorics, Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that ( 1 / 2 )n2 / k-1-n / 2≤f(n,k) ≤2 n(n-2) / k-2. For the case when k=n, we show that 2 ≤f(n,n) ≤3. For the case when k=n and G is a geometric graph on a set of points in convex position, we completely solve the problem and prove that at least three edges must be removed.

Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every non-convex simple polygon has a vertex that can be continuously moved such that during the process no vertex-vertex visibility is lost and some vertex-vertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertex-vertex visibility during the process?

We show that for each integer $g\geq0$ there is a constant $c_g > 0$ such that every graph that embeds in the projective plane with sufficiently large face–width $r$ has crossing number at least $c_g r^2$ in the orientable surface $\Sigma_g$ of genus $g$. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.

Kano et al. proved that if P0, P1, ..., Pk−−1 are pairwise disjoint collections of points in general position, then there exist spanning trees T0, T1, ..., Tk−−1, of P0, P1, ..., Pk−−1, respectively, such that the edges of T0∪T1∪...∪Tk−1 intersect in at most (k – 1)n – k(k – 1)/2 points. In this paper we show that this result is asymptotically tight within a factor of 3/2. To prove this, we consider alternating collections, that is, collections such that the points in P:=P0∪P1∪...∪Pk−1 are in convex position, and the points of the Pi’s alternate in the convex hull of P.

Sea G = (V (G), E(G)) una gráfica simple, en el que V (G) y E(G) son sus conjuntos de vértices y aristas respectivamente. Si S ⊆ V (G), sea B(S) el conjunto de vértices con- tenido en V (G)\S con algún vecino en S. El diferencial de S denotado por ∂(S) se define como |B(S)| −|S|, y el diferencial de una gráfica como ∂(G) = m ́ax{∂(S) : S ⊆ V (G)}. En este trabajo mostramos una amplia colección de resultados que relacionan el dife- rencial con parámetros bien conocidos, como el número de dominación, orden, tamaño, grado, cuello, entre otros. También estudiamos el diferencial en la gráfica R(G), que se obtiene a partir de G, agregando un nuevo vértice por cada arista de G y uniendo cada vértice nuevo a los extremos de la arista correspondiente a él. Encontramos cotas para ∂(R(G)) y familias infinitas de gráficas que las alcanzan. Además, mostramos relaciones interesantes entre ciertos conjuntos de vértices de G y R(G). Generalizamos el concepto de diferencial de una gráfica. Estudiamos las propiedades matemáticas de este nuevo parámetro y encontramos cotas que lo relacionan con el orden, tamaño, grado mínimo (máximo) y el número de dominación. Finalmente, este trabajo se complementa con el concepto de polinomio diferencial, establecemos relaciones entre el polinomio y sus coeficientes, y mostramos fórmulas del polinomio diferencial en ciertas clases de gráficas.

Dada una gráfica G de orden n ≥ 3, se define a F2(G) como la gráfica cuyo conjunto de vértices consiste de todos los 2-subconjuntos de V (G), y dos vértices X, Y de F2(G) serán adyacentes si y solo si la diferencia simétrica de X y Y consta de dos vértices que son adyacentes en G. Hasta donde sabemos, la gráfica F2(G) fue introducida por Johns en 1988 [43]. Posteriormente, en 1991 Alavi et al. [2], la definieron con el nombre de gráfica de doble vértice. En 2002, T. Rudolph [62] redefinió la misma gráfica bajo el nombre de el cuadrado simétrico de G. Similarmente, si en lugar de los 2-subconjuntos de V (G), se consideran los k-subconjuntos de V (G), donde k є {2 ,..., n - 1}, entonces obtenemos la gráfica Fk(G) que se llama la k-potencia simétrica de G [9]. En [27] Fabila-Monroy et. al., a Fk(G) la llamaron gráfica de k-fichas de G. Como se puede verificar en [3, 4, 6, 8, 9, 17, 18, 27, 39, 48, 52, 37, 53, 62, 66, 67] y las referencias contenidas en esos artículos, el interés en las gráficas Fk(G) ha generado una gran cantidad de investigaciones en muchas ramas de las matemáticas discretas. Una de las líneas de investigación con mayor actividad consiste en estimar o determinar el valor exacto de diversos parámetros combinatorios de Fk(G). En este trabajo se presentan algunos resultados originales sobre la estimación de dos de estos parámetros: el número de dominación y el número de empaquetamiento de F2(Pn) y F3(Pn), en donde Pn denota a la gráfica camino de orden n. El resultado principal de esta tesis consiste en la determinación del valor exacto del número de empaquetamiento de F2(Pn). Este resultado tiene como consecuencia la confirmación de una conjetura de Rob Pratt sobre el tamaño máximo que puede tener un código binario de longitud n y peso constante 2 que es 1-corrector para una transposición adyacente, y ha sido publicado en [30]. En particular, esta conjetura proponía la función generatriz ordinaria correspondiente a la secuencia A085680 en la OEIS (The On-Line Encyclopedia of Integer Sequences) [59].