FoCM 2014 conference
Session A4 - Graph Theory and Combinatorics
Organizers: Yoshiharu Kohayakawa (University of São Paulo, Brazil) - Gelasio Salazar (University of San Luis Potosí, México) - Jayme Szwarcfiter (Federal University of Rio de Janeiro, Brazil)
Talks
December 11, 14:30 ~ 15:00 - Room B11
Improved upper bounds on the crossing number, the 2-page crossing number and the rectilinear crossing number of the hypercube
Celina Figueiredo
UFRJ, Brazil - celina@cos.ufrj.br
The $n$-cube $Q_n$ has as vertices all binary strings of length $n$, and there is an edge between two strings if and only if they differ in precisely one position. Very little is known about exact values of the crossing number (the minimum number of crossings in a drawing in the plane), the 2-page crossing number, and the rectilinear crossing number for $Q_n$. We exhibit drawings that are in line with the crossing number conjecture of Erdős and Guy. We also exhibit 2-page and rectilinear drawings, surprisingly with the same number of crossings, despite being completely different constructions.
Joint work with Luerbio Faria (State University of Rio de Janeiro, Brazil), Ondrej Sýkora (Loughborough University, UK), Imrich Vrt'o (Slovak Academy of Sciences, Slovak Republic) and Bruce Richter (University of Waterloo, Canada).
December 11, 15:00 ~ 15:30 - Room B11
On the directed cycle double cover conjecture
Andrea Jiménez
University of São Paulo, Brazil - apjr.andrea@gmail.com
Given a graph $G$, let $D(G)$ denote the direct graph obtained from $G$ by replacing each edge of $G$ by a pair of arcs oppositely directed. The famous directed cycle double cover conjecture, formulated by Jaeger, asserts that if $G$ is a graph without bridges, then the set of arcs of $D(G)$ can be partitioned into directed cycles. In this talk we discuss our recent progress towards a proof of Jaeger's conjecture.
Joint work with Martin Loebl (Charles University, Czech Republic).
December 11, 15:30 ~ 16:00 - Room B11
Monochromatic path/cycle partitions
Maya Stein
University of Chile, Chile - mstein@dim.uchile.cl
A conjecture of Gyárfás says that given any colouring with $r$ colours of the edges of the complete graph $K_n$ on $n$ vertices, there are $r$ disjoint monochromatic paths that induce a partition of $V(K_n)$. The conjecture is true for $r\leq3$. Replacing paths with cycles, it is known that in general, the number of cycles needed is greater than $r$, but can be bounded by a function of $r$. (Here, single vertices/edges count as cycles.) For $r=2$, it is known that $2$ paths/cycles suffice.
This talk gives an overview on the history of the problem. We then describe some recent results for bipartite and multipartite graphs, with fixed values of $r$. We also study variants of the problem for $r$-local colourings, and for $r$-mean colourings. The results mentioned are joint work with Conlon, with Lang, with Lang and Schaudt, and with Schaudt, respectively.
December 11, 16:00 ~ 16:30 - Room B11
On Connected Identifying Codes for Infinite Lattices
Victor Campos
ParGO - Universidade Federal do Ceará, Brazil - campos@lia.ufc.br
An identifying code in a graph $G$ is a set $C$ of vertices of $G$ such that the closed neighbourhood of every vertex contains a unique and non-empty subset of $C$. We say that $C$ is a connected identifying code if $G[C]$ is connected. We prove that if a finite graph $G$ on $n$ vertices has maximum degree $\Delta$, then any connected identifying code $C$ satisfies $|C| \ge \frac{2n-2}{\Delta+1}$. We also show this bound is best possible and that the coefficient of $n$ cannot be improved for $\Delta$-regular graphs. We also show that the minimum density of connected identifying codes for the infinite triangular, hexagonal and square lattices are $\frac{1}{3}$, $\frac{1}{2}$ and $\frac{2}{5}$, respectively.
Joint work with Fabrício Benevides (ParGO - Universidade Federal do Ceará), Mitre Dourado (Universidade Federal do Rio de Janeiro), Rudini Sampaio (ParGO - Universidade Federal do Ceará) and Ana Silva (ParGO - Universidade Federal do Ceará).
December 11, 17:00 ~ 17:30 - Room B11
Toughness and Kronecker product of graphs
Daniel A Jaume
Universidad Nacional de San Luis, Argentina - djaume@unsl.edu.ar
When investigating the vulnerability of a communication network (graph) to disruption, one may want to find the answer of the following questions (there may be others)
What is the number of elements that are not functioning?
What is the number of remaining connected subnetworks (graphs)?
What is the size of a largest remaining group within mutual communication can still occur (the size of a largest remaining connected component)?
Many graph theoretical parameters such as connectivity, toughness, scattering number, integrity, tenacity, rupture degree, and their edge-analogues, have been defined to obtain the answers to these questions. These parameters have been used to measure the vulnerability of a graph (network)
For most of these parameters, the corresponding computing problems are NP-hard. In this work we generalized a result of Mamut and Vumar, for the toughness of Kronecker product of graphs (Vertex vulnerability parameters of Kronecker products of complete graphs, Information Processing letters 106 (2008) 258-262):
Theorem: Let $G$ be a graph with $t(G)\geq n\geq 3$, then $t(G\times K_n)=n-1$
Joint work with Adrián Pastine (Michigan Technological University).
December 11, 18:00 ~ 18:30 - Room B11
Transversals to the convex hulls of $k$-sets
Luis Montejano
National University of Mexico, Juriquyilla, Mexico - luismontej@gmail.com
What is the maximum positive integer $n$ such that every set of $n$ points in $\mathbb{R}^{d}$ has the property that the convex hulls of all $k$-sets have a transversal $(d-\lambda )$-plane? In this paper, we investigate this and closely related questions. We define a special Kneser hypergraph and by using some topological results and the well-known $\lambda$-Helly property, we relate our question with the chromatic number of the Kneser hypergraph, and we establish a connection $(\lambda=1)$ with so called Kneser's conjecture, first proved by Lovász. This problem is all connected with Gale embeddings, the discrete version of Rado’s Problem, and with cyclic polytopes.
Joint work with J. L. Arocha, J. Bracho, J. Chaperon, Leo Martínez, J. Ramirez-Alfonsin and L. P. Montejano.
December 11, 18:30 ~ 19:00 - Room B11
The Li-Yau inequality and the geometry of graphs
Paul Horn
University of Denver, United States - paul.horn@du.edu
Harnack inequalities relate the maximum and minimum values of eigenfunctions or positive solutions to the heat equation. These are classical in the manifold setting, and versions are also known for functions on graphs. It is known that a graph satsifying a so-called parabolic Harnack inequality is equivalent to the graph satisfying certain (hard to check) geometric conditions. In the non-negatively curved manifold case, the Li-Yau inequality is a stronger (local) gradient estimate which implies the (global) Harnack inequality. In this talk we describe a similar gradient estimate for graphs.
Along the way, we discuss the issue of defining curvature for graphs and some of the difficulties that arise when transferring a continuous result into a discrete setting along with some additional results on graphs.
Joint work with Frank Bauer (Harvard University), Gabor Lippner (Northeastern University), Yong Lin (Renmin University), Dan Mangoubi (Hebrew University) and Shing-Tung Yau (Harvard University).
December 12, 14:35 ~ 15:25 - Room B11
Homomorphisms, Ramsey Theory and Limits
Jaroslav Nešetřil
Charles University, Czech Republic - nesetril@kam.mff.cuni.cz
We present three results from three areas (suggested by the title) which, at least at first glance, have little in common. We shall try to convince the audience of the opposite. Some of the key words: sparse-dense dichotomy, Ramsey classes, structural limits.
December 12, 16:00 ~ 16:30 - Room B11
On the Number of Perfect Matchings in Graphs
Marcelo Carvalho
Universidade Federal de Mato Grosso do Sul, Brasil - mhc@facom.ufms.br
In this talk, we survey the main results on the problem of determining the number of perfect matchings in graphs. This problem has been relatively well studied, specially for cubic graphs, but not much is known in the general case. We shall present some new results in the general case and some challenging problems.
Joint work with Cláudio L. Lucchesi (Universidade Federal de Mato Grosso do Sul, Brasil) and U. S. R. Murty (University of Waterloo, Canada).
December 12, 17:00 ~ 17:30 - Room B11
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs
Guillermo Durán
University of Buenos Aires, Argentina - gduran@dm.uba.ar
A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties.
In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs.
We analyze a variation of perfect graphs, clique-perfect graphs, and three subclasses of perfect graphs, coordinated graphs, balanced graphs, and neighborhood perfect graphs.
December 12, 17:30 ~ 18:00 - Room B11
Characterizing and Recognizing Normal Helly Circular-Arc Graphs
Luciano Grippo
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina - lgrippo@ungs.edu.ar
In this work, we study the intersection graphs of finite sets of arcs on a circle no three of which cover the circle, known as normal Helly circular-arc graphs. Those circular-arc graphs which are minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs were identified by Lin, Soulignac, and Szwarcfiter, who also posed the problems of determining the remaining minimal forbidden induced subgraphs and finding a direct recognition algorithm. In this work, we solve their problems, obtaining the complete list of minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs, and presenting a direct recognition algorithm which also finds, in linear time, when the input is a normal Helly circular-arc graph, a minimal forbidden induced subgraph as certificate.
Joint work with Yixin Cao (Department of Computing, Hong Kong Polytechnic University) and Martín Darío Safe (Instituto de Ciencias, Universidad Nacional de General Sarmiento).
December 12, 18:00 ~ 18:30 - Room B11
Algorithms and complexity of graph convexity problems
Vinícius dos Santos
Centro Federal de Educação Tecnológica de Minas Gerais, Brazil - viniciussantos@decom.cefetmg.br
Several results concerning convex sets, originally studied on the Euclidean space, have been generalized for abstract convexities. In particular, the results of Carathéodory, Helly and Radon are among the most famous and well-studied. In the last forty years, graph convexities have been studied and graph analogues of classical results have been obtained. More recently, computational aspects have been the focus of many papers of this area.
In this talk we highlight some algorithmic and complexity results of convexity parameters on graphs, discuss some relations with conversion problems and present some open problems.
Joint work with Jayme L. Szwarcfiter (Universidade Federal do Rio de Janeiro, Brazil).
December 13, 14:30 ~ 15:00 - Room B11
On the applications of counting independent sets in hypergraphs
Jozsef Balogh
UIUC, USA - jobal@math.uiuc.edu
Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs. During the talk, I show a recent application of the method; solving the following Erdős problem: What is the number of maximal triangle-free graphs?
If there is some extra time in the talk, I will survey some other recent applications.
These applications are partly joint with Das, Delcourt, Liu, Mycroft, Petrickova, Sharifzadeh and Treglown.
December 13, 15:00 ~ 15:30 - Room B11
An Erdős-Lovász-Spencer Theorem for permutations and its consequences for parameter testing
Carlos Hoppen
Universidade Federal do Rio Grande do Sul, Brazil - choppen@ufrgs.br
The classical theorem of Erdős, Lovász and Spencer [Strong independence of graphcopy functions, Graph Theory and Related Topics, Academic Press (1979), 165--172] asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and apply the methods used in its proof to give an example of a permutation parameter that is both bounded and testable, but not finitely forcible.
Joint work with Roman Glebov (ETH Zürich, Switzerland), Tereza Klimošová (University of Warwick, United Kingdom), Yoshiharu Kohayakawa (Universidade de São Paulo, Brazil), Daniel Král (University of Warwick, United Kingdom) and Hong Liu (University of Illinois at Urbana-Champaign, United States).
December 13, 15:30 ~ 16:00 - Room B11
Constructing covering arrays from $m$-sequences
Daniel Panario
Carleton University, Canada - daniel@math.carleton.ca
Let $q$ be a prime power and $\mathbb{F}_q$ the finite field of $q$ elements. A $q$-ary $m$-sequence is a periodic sequence of elements from $\mathbb{F}_q$, which is generated by a linear recurrence relation of order $n$, and has maximal period $q^n-1$. These sequences play a crucial role in a wide variety of communications and cryptographic applications.
A covering array $CA(N; t; k; v)$ is a $N \times k$ array with entries from an alphabet of size $v$, with the property that any $N \times t$ sub-array has at least one row equal to every possible $t$-tuple. Covering arrays are used in applications such as software and hardware testing. It is crucial for such applications to find covering arrays $CA(N; t; k; v)$ with the smallest $N$ possible, for given $t, k, v$.
There are various algebraic and combinatorial constructions, as well as computer generation methods for covering arrays. Although constructions using $m$-sequences exist in the literature, these are a few and, until recently, only focused on similar combinatorial objects (``orthogonal arrays'' that are covering arrays with more restrictions). Moura, Raaphorst and Stevens (2013) give a construction for covering arrays of strength 3 using $m$-sequences, which are the best known for many cases. For any prime power $q$, they give a covering array of strength $t = 3$ with $k = q^2 + q + 1$ columns over $v = q$ symbols that has size $N = 2q^3-1$ (number of rows).
In this talk we present an extension of this construction to strengths greater than or equal to 4. The construction is based on Linear Feedback Shift Register (LFSR) sequences constructed using primitive polynomials over finite fields. We have also developed a backtracking algorithm that yields new covering arrays of strength 4. For certain parameters, these are either the best, or close to being the best known when compared to the best known covering array tables kept by Colbourn. Furthermore, our findings show interesting connections with finite geometry.
Joint work with Lucia Moura (University of Ottawa, Canada), Brett Stevens (Carleton University, Canada) and Georgios Tzanakis (Carleton University, Canada).
December 13, 16:00 ~ 16:30 - Room B11
A unified approach to linear probing hashing
Alfredo Viola
Universidad de la República, Uruguay - viola@fing.edu.uy
We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. The Poisson Transform links in a natural way both approaches. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on $q$-calculus) to directly derive the generating functions to analyze.
Joint work with Svante Janson (Uppsala University, Sweden).
December 13, 17:05 ~ 17:55 - Room B11
Extremal combinatorics in random discrete structures
Mathias Schacht
Universität Hamburg, Germany - schacht@math.uni-hamburg.de
We survey on recent results at the intersection of extremal combinatorics and random graph theory. More precisely, we consider thresholds for extremal properties of random discrete structures. Among other problems, we shall discuss the threshold for Szemerédi's theorem on arithmetic progressions in random subsets of the integers and the threshold for Turán-type problems for random graphs and hypergraphs, which were obtained independently by Conlon and Gowers and by the speaker. Furthermore, we discuss recent general results on independent sets in hypergraphs by Balogh, Morris and Samotij and by Thomason and Saxton, which led to new proofs of these results and have already had many other applications in the area.
December 13, 18:05 ~ 18:55 - Room B11
Towards a Broader View of Theory of Computing -- Part 2
Narendra Karmarkar
Indian Institute of Technology, Bombay, India - narendrakarmarkar@yahoo.com
Beginning with the projectively invariant method for linear programming, interior point methods have led to powerful algorithms for many difficult computing problems, in combinatorial optimization, logic, number theory and non-convex optimization. Algorithms for convex optimization benefitted from many pre-established ideas from classical mathematics, but non-convex problems require new concepts. This three part series outlines some of these concepts -- computational models based on the concept of the continuum, algorithms invariant with respect to transformations on co-ordinate representation-projective, bi-rational, and bi-holomorphic transformations, extended proof systems for more efficient certificates of optimality, extensions of Grassmann’s extension theory, efficient evaluation methods for the effect of exponential number of constraints, theory of connected sets based on graded connectivity, theory of curved spaces adapted to the problem data, and concept of “relatively” algebraic sets in curved space.
Topics for part 2 - In this session, we show how algorithms based on continuum computing can obtain exponential speed-up over those based on Turing machines by considering concrete examples of finding maximum independent set in a graph and the satisfiability problem. We review the concept of graph minors based on parity-respecting homeomorphisms. Although there can be exponential number of subgraphs homeomorphic to a given minor, we show how their combined effect can be computed in polynomial number of operations in the continuum approach.
We extend the concept of graph minors to sub-formulas in a satisfiability problem. As shown by Chvátal and Szemerédi, almost all instances of the problem for certain range of parameter require exponential time for resolution. We identify sub-formulas, which we call “mobius cycles”, as the culprits causing exponential behavior, and show that their combined effect can be computed in polynomial number of operations in the continuum approach. The method can be thought of as generalizing the generating functions used in enumerative combinatorics to continuum based algorithms. Objective function for these problems is treated by non-convex optimization methods covered in part 3.
Ability of algebroid functions to efficiently encode and process information regarding exponential number of combinatorial substructures should not come as a surprise, given that the most famous meromorphic function -- the Riemann Zeta function -- is able to carry information regarding the infinite sequence of primes.
Posters
Covering edge multicolorings of complete graphs with monochromatic connected components
Sebastián Bustamante
Universidad de Chile, Chile - sbustamante@dim.uchile.cl
Let $K_n$ denote the complete graph on vertex set $V = [n].$ An $r$-edge multicoloring is a coloring of the edges with any number of colors in $[r].$ If every edge is colored by a constant number $k$ of colors, we say that the $r$-edge multicoloring is $k$-regular. The connected components of the monochromatic graphs given by $G_i = (V_i,E_i),$ with $e \in E_i$ if the edge $e$ has the color $i,$ for $i \in [r],$ are called monochromatic connected components. For $r > k,$ let $f(r,k)$ the smallest number such that, for any $k$-regular $r$-edge multicoloring of a complete graph, it is possible to cover the complete graph by $f(r,k)$ monochromatic connected components. A reformulation of an important special case of Ryser's conjecture states that $f(r,1) = r-1$ for all $r.$ This conjecture is known to be true for $r \leq 5.$ We prove, for $k \geq 2,$ several exact values and bounds for $f(r,k),$ and a related result of independent interest, as the maximum number of vertices for a vertex minimal $r$-edge multicoloring of a complete graph coverable by three, but no by two, monochromatic connected components.
Joint work with Maya Stein (Universidad de Chile, Chile).
Alignments of a Pair of Graphs
Cesim Erten
Kaidr Has University, Turkey - cesimerten@gmail.com
The graph alignment problem has important applications in biological network alignment. In the case of protein-protein interaction networks for instance, undirected graphs $G_1, G_2$ correspond to PPI networks from a pair of species, where each of the vertex sets $V_1, V_2$ represent the sets of proteins, and $E_1, E_2$ represent respectively the sets of known protein interactions pertaining to the networks of species under consideration. The informal goal is to find a one-to-one mapping between $V_1, V_2$ that maximizes the conservation of interactions between the pairs of mappings. A specific version of the problem reduces the size of the problem by restricting the output alignment mappings to those chosen among certain subsets of protein mappings. The "constrained graph alignment" is considered a graph theoretical generalization of this biological network alignment problem.
Let $G_1=(V_1,E_1), G_2=(V_2,E_2)$ be undirected graphs and $S$ be a bipartite graph defined on $(V_1,V_2)$ as the partition. For $S$, assume the degree of each vertex from the part $V_i$ is at most $m_i$, for $i=1,2$. A {\it legal alignment} $A$ is a matching of $S$. Let $u_1u_2,v_1v_2$ be a pair of edges of $A$ such that $u_1,v_1\in V_1$ and $u_2,v_2 \in V_2$. This pair of edges gives rise to a {\it conserved edge} if and only if $u_1v_1 \in E_1$ and $u_2v_2 \in E_2$. The constrained alignment problem is that of finding a legal alignment that maximizes the number of conserved edges. A 4-cycle $x$ denoted with $c_4(x)=abcd$ is a cycle $a-b-c-d-a$ where $ab\in E_1$, $cd \in E_2$ and $ad,bc \in S$. We say that two $c_4$s "conflict" if their edges from $S$ cannot coexist in any legal alignment; the $c_4$s contain at least one pair of $S$ edges which cannot coexist in a matching of $S$. For a given $\prec$$G_1,G_2,S$$\succ$ instance, we construct a "conflict graph", $\mathcal{C}$, as follows: For each $c_4$ create a vertex in $\mathcal{C}$ and for each pair of conflicting $c_4$s create an edge between their respective vertices in $\mathcal{C}$. With this construction, the constrained alignment problem obviously reduces to the maximum independent set problem. Let $\mathcal{M}$ be and independent set of the conflict graph $\mathcal{C}$. The set of $S$ edges included in the $c_4$s corresponding to the vertices in $\mathcal{M}$ constitute an optimum solution of the constrained alignment instance $\prec$$G_1,G_2,S$$\succ$, that is a legal alignment with the maximum number of conserved edges, if and only if $\mathcal{M}$ is a maximum independent set of $\mathcal{C}$. The following results apply to the case where $m_2=1$, that is each vertex of $G_2$ can be mapped to a single vertex of $G_1$. Fertin et al. studied the constrained alignment problem under the same setting, that is $m_2=1$. Although they also define a conflict graph and provide a fixed-parameter tractability result based on a simple argument regarding the degrees of the conflict graphs, they do not provide any further structural properties. In what follows we extend their results and provide several graph-theoretic properties of conflict graphs arising from possible constrained alignment instances under various restrictions. Such properties are useful in applying relevant maximum independent set results. We skip all the proofs due to space restrictions.
Denote a k-cycle with $C_k$ and denote the complement of $G$ with $\overline{G}$. A "weakly triangulated" graph contains neither a $C_k$ nor $\overline{C_k}$, for $k\geq 5$. The following theorem in connection with the "strong perfect graph theorem" of Chudnovsky et al. implies that the conflict graphs under the considered setting are perfect.
Theorem: If $G_1$ is acyclic and $m_2=1$ then $\mathcal{C}$ is weakly triangulated.
Below we present graph theoretic properties of conflict graphs removing any restriction on $G_1$ or $G_2$, but imposing a further constraint on $m_1$.
Theorem: If $m_1=2$ and $m_2=1$, the wheel $W_k, k\ge5$ is not an induced subgraph of a conflict graph.
We now generalize the previous results by providing further structural properties of conflict graphs for the more general case where $m_1$ can be any positive integer constant. We first present our result analogous to the previous theorem.
Theorem: If $m_2=1$, $W_k$ is not an induced subgraph of $\mathcal{C}$, for $k\geq 7$.
Next we present our results regarding the existence of cliques as subgraphs of conflict graphs for any $m_1$. Theorem: If $m_2=1$, the maximum size of any clique in $\mathcal{C}$ is $m_1^2$.
The following result characterizes the conflict graphs that do not contain certain claws as induced subgraphs. A d-claw is an induced subgraph of an undirected graph, that consists of an independent set of $d$ vertices, called $talons$, and the $center$ vertex that is adjacent to all vertices in this set. Let $\Delta_{min}=min(\Delta_1, \Delta_2)$, where $\Delta_1, \Delta_2$ are the maximum degrees of $G_1$ and $G_2$ respectively.
Theorem: If $m_2=1$, $(2\Delta_{min}+2)$-claw is not an induced subgraph of $\mathcal{C}$.
Joint work with Ferhat Alkan (University of Copenhagen, Denmark), Turker Biyikoglu (Izmir Institute of Technology, Turkey) and Marc Demange (RMIT University, Australia).
Characterizations of ($k$)-interval graphs
Florencia Fernández Slezak
Instituto de Cálculo, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina - ffslezak@gmail.com
Keywords: unit interval graphs, intersection graphs.
A graph $G$ is an interval graph iff its vertices can be put in a one to one correspondence with a family of intervals on the real line such that two vertices in $G$ are adjacent if and only if their corresponding intervals intersect. Such a family of intervals is called an interval model for $G$ [1, 2].
If there is an interval model for graph $G$ such that the intervals are of unit length, then it is called a \emph{unit interval model} and $G$ is a \emph{unit interval graph}. A theorem was proved which establishes that $G$ is a unit interval graph if and only if $G$ is an interval graph containing no induced claw, that is, $K_{1,3}$ [6, 7].
A unit interval graph is an interval graph which admits a representation where all elements have the same length. It is known that a model with intervals of the same length and integer extremes can be built in $\mathcal{O}(n + m)$ time to represent a given unit interval graph [4, 5]. Let $k \in \mathbb{N}_0$, we define $G$ as a ($k$)-interval graph iff $G$ is a unit interval graph which admits a model of open intervals of length $k$ and integer extremes. Likewise, we define the [$k$]-interval graphs as those unit interval graphs which admit a model with the same characteristics but with closed intervals.
In this work, we present a structural characterization of the simplicial vertices in a unit interval graph without twins, which leads to a characterization of the ($k$)-interval graphs. We study the structure of these graphs, finding forbidden induced subgraphs, thus a theorem fully characterising this class is posed, finding the least $k$ such that $G$ is a ($k$)-interval graph.
Moreover, the ($k$)-interval graphs will be studied as induced subgraphs of power of paths, continuing with the results obtained by Lin, Rautenbach, Soulignac and Szwarcfiter [3].
Furthermore, an equivalence between the [$k$]-interval and the ($k$)-interval graphs will be set, which allows us to use the obtained results for open intervals as well as closed intervals.
Finally, we will present open problems we are studying at the moment.
References:
[1] Golumbic, M. C., Algorithmic graph theory and perfect graphs, Academic Press New York (1980)
[2] Lekkerkerker, C. and Boland, D., Representation of finite graphs by a set of intervals on the real line, FundMath, 51, 45--64 (1962).
[3] Lin, M. C., Rautenbach, D., Soulignac, F., Szwarcfiter, J. L., Powers of Cycles, Powers of Paths, and Distance Graphs, Discrete Applied Mathematics, 159, 621--627 (2011).
[4] Lin, M. C., Soulignac, F. J., Szwarcfiter, J. L., Short Models for Unit Interval Graphs, Electronic Notes in Discrete Mathematics, Amsterdam, 35, 247--255 (2009).
[5] Corneil, D. G., Kim, H., Natarajan, S., Olariu, S., Sprague, A. P., Simple linear time recognition of unit interval graphs, Information Processing Letters, 55, 99--104 (1995).
[6] Roberts, F. S., Indifference graphs, in: Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., Academic Press, New York, 139--146 (1968).
[7] Gardi, F., The Roberts characterization of proper and unit interval graphs, Discrete Mathematics, 22(307), 2906 -- 2908 (1968).
Joint work with Guillermo Durán (Universidad de Buenos Aires and Universidad de Chile), Luciano Grippo (Universidad Nacional de General Sarmiento), Fabiano Oliveira (Universidade do Estado do Rio de Janeiro) and Jayme Szwarcfiter (Universidade Federal do Rio de Janeiro).
Local EPT graphs on bounded degree trees
María Pía Mazzoleni
Universidad Nacional de La Plata, CONICET, Argentina - pia@mate.unlp.edu.ar
A graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. An EPT representation of G is a pair $\langle \mathcal{P},T \rangle$ where $\mathcal{P}$ is a family $(P_v)_{v\in V(G)}$ of subpaths of the host tree T satisfying that two vertices v and v' of G are adjacent if and only if $P_v$ and $P_{v'}$ have at least two vertices (one edge) in common. When the maximum degree of the host tree T is at most h, the EPT representation of G is called an (h,2,2)-representation of G. The class of graphs which admit an (h,2,2)-representation is denoted by [h,2,2].
Notice that the class of EPT graphs is the union of the classes [h,2,2] for $h\geq 2$. It was proved that the recognition of EPT graphs is an NP-complete problem.
The EPT graphs are used in network applications, where the problem of scheduling undirected calls in a tree network is equivalent to the problem of coloring an EPT graph.
In this paper, we examine the local structure of paths passing through a given vertex of a host tree which has maximum degree h, and show these locally EPT graphs are equivalent to the line graphs of certain graphs.
Definition: Let $\langle \mathcal{P},T \rangle$ be an EPT representation of a graph G. A pie of size n is a star subgraph of T with central vertex q and neighbors $q_1$,...,$q_{n}$ such that each "slice" $q_i\,q\,q_{i+1}$ for $1 \leq i \leq n$ is contained in a different member of $\mathcal{P}$; addition is assumed to be module n.
Let $\langle \mathcal{P},T \rangle$ be an EPT representation of a graph G. It was proved that if G contains a chordless cycle of length $n\geq 4$, then $\langle \mathcal{P},T \rangle$ contains a pie of size n.
Definition: We say that $\langle \mathcal{P},T \rangle$ is a local EPT representation of G if it is an EPT representation where all the paths of $\mathcal{P}$ share a common vertex of T.
We call G a local EPT graph if it has a local EPT representation.
Let $h\geq 5$, we say that G belongs to the class [h,2,2] local if and only if G has a local EPT representation in a host tree T with maximum degree h.
In this work, we characterize the graphs which belongs to the class [h,2,2] local.
Definition: Let G be a connected graph. We say that $v\in V(G)$ is a cut vertex of G if G-v has at least two connected components.
Theorem 1: Let $h\geq 5$. If $G\in [h,2,2]$ local and $G\notin [h-1,2,2]$ then G has no cut vertices.
We show that this special subclass of EPT graphs is equivalent to the class of line graphs of certain graphs which have certain properties.
Definition: Let H be a graph, the line graph of H, noted by L(H), has vertices corresponding to the edges of H with two vertices adjacent in L(H) if their corresponding edges of H share an endpoint.
Definition: We say that two vertices u,v of G are adjacent dominated vertices if $uv\in E(G)$ and $N_G(u)\subseteq N_G(v)$ or $N_G(v)\subseteq N_G(u)$.
Theorem 2: Let $h\geq 5$. $G\in [h,2,2]$ local, $G\notin [h-1,2,2]$ and G without adjacent dominated vertices if and only if G=L(H) with H a graph such that:
(i) |V(H)|=h; (ii) H has no vertices of degree 1; (iii) H is simple; (iv) H has no adjacent dominated vertices; (v) H has a cycle $C_n$, with $4 \leq n\leq h$; and every vertex of $H-C_n$ is in some path between two different vertices of $C_n$.
Conjecture: Let $h\geq 5$. If $G\in [h,2,2]$, $G\notin [h-1,2,2]$ but $G-v\in [h-1,2,2]$, for all $v\in V(G)$, then $G\in [h,2,2]$ local.
Joint work with Liliana Alcón (Universidad Nacional de La Plata, Argentina) and Marisa Gutierrez (Universidad Nacional de La Plata, CONICET, Argentina).
Methods for reliability analysis of diameter constrained networks
Denis Migov
Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Russia - mdinka@rav.sscc.ru
Networks where the edges are a subject to random failures are studied in the present article. As a rule networks with unreliable elements are modeled by a probabilistic graph in which an operational probability is associated with every element (a node or an edge). The most common reliability measure of such networks is the probability that all the terminal nodes in a network can keep connected together, given the reliability of each network node and edge. The analysis of the network reliability has been a subject of considerable research [1, 2, 3]. Today we have a lot of different methods for network reliability calculation and evaluation. These methods may be useful during network topology design and optimization.
In practice it often needs not only the existence of a path between each pair of nodes, but the existence of a path passing via a limited number of communication links. Thus, we arrive to a different reliability measure. The diameter constrained network reliability (DCNR) is a probability that every two nodes from a given set of terminals are connected with a path of length less or equal to a given integer. By the length of a path we understand the number of edges in this path.
This reliability measure was introduced in [4] and studied in more detail in [5, 6]. The problem of computing this measure in general is known to be NP-hard, just like the problem of computing the probability of network connectivity. Now the complexity of DCNR calculation is completely studied [6].
The new approach in reliability calculation (without diameter constraint) was introduced in [2]: cumulative update of lower and upper bounds of network reliability for faster feasibility decision. This method allows to decide the feasibility of a given network without performing exhaustive calculation. The approach was further developed with the help of network decomposition [3]. We propose the method for cumulative updating of lower and upper bounds of diameter constrained network reliability. This method allows us to make a decision about the network reliability (or unreliability) with diameter constraint with respect to a given threshold without performing the exhaustive calculation.
One of the main reasons, which make the calculation of diameter constrained network reliability much more complicated in comparison with other network reliability measures, is the lack of methods of recursion quantity decrease. For example, for k-terminal network reliability calculation we may use a lot of network reduction and decomposition methods. We propose to use the decomposition methods and some other techniques for DCNR calculation. Let us demonstrate one of these methods.
Suppose that graph $G$ includes cutnode $x$ dividing the graph in two $G_1$ and $G_2$ subgraphs. Let us consider 2-terminal case. Let terminals $s$ and $t$ belong to $G_1$ and $G_2$ respectively and none of them is $x$. DNCR is defined as the probability that nodes $s$ and $t$ are connected with diameter constrain $d$ in a graph $G$. We denote it by $ R_{s, t} ^d(G) $. By $R_{s,t}^{\overline{d}}(G)$ we denote a probability that nodes $s$ and $t$ are connected in $G$ and a length of shortest path between them is equal to $d$. By $d_i$ we denote the distance between $s$ and $x$ or $y$ in subgraph $G_i$. We obtained how $R_{s,t}^d(G)$ is expressed in terms of $R_{s, x}^i(G_1)$, $ R_{s, x}^{\overline{i}}(G_1)$, $R_{x,t}^i(G_2)$, and $R_{x, t}^{\overline{i}}(G_2)$: \begin{equation} R^{d}_{s,t}(G)=\sum^{d-d_2}_{i=d_1}R^{\overline{i}}_{s,x}(G_1)R^{d-i}_{x,t}(G_2) \label{ArtFormula} =\sum^{d-d_1}_{i=d_2}R^{d-i}_{s,x}(G_1)R^{\overline{i}}_{x,t}(G_2). \end{equation}
Also we obtained some other effective techniques for DCNR calculation, including the formula that lets performing decomposition for the computation of diameter constrained 2-terminal reliability of a network that contains 2-node cuts. While the calculation of DCNR known to be a NP-hard problem, the proposed methods allow to considerably reduce the calculation time.
This work was supported by Russian Foundation for Basic Research under Grant 14-07-31069 and by Novosibirsk city administration under Grant 39-14.
References
1. Ball M.O. Computational complexity of network reliability analysis: An overview // IEEE Transactions on Reliability. Vol. 35, 1986, p. 230-239.
2. Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Transactions on Reliability. Vol. 59, issue 3, 2010, 551-562.
3. Rodionov A.S., Migov D.A., Rodionova O.K. Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. Vol. 61, issue 2, 2012, p. 460-465.
4. Cancela H., Petingi L. Diameter Constrained Network Reliability: Exact Evaluation by Factorization and Bounds // Proc. Int. Conf. on Industrial Logistics. Japan, 2001, p. 359-356.
5. Migov D.A. Computing Diameter Constrained Reliability of a Network with Junction Points // Automation and Remote Control. Vol. 72, issue 7, 2011, p. 1415-1419.
6. Eduardo Canale, Hector Cancela, Franco Robledo, Gerardo Rubino and Pablo Sartor. On Computing the 2-diameter-constrained K-reliability of Networks // International Transactions in Operational Research. Vol. 20, issue 1, January 2013, p. 49-58.
Counting $k$-uniform linear hypergraphs in sparse pseudorandom hypergraphs
Guilherme Oliveira Mota
USP - University of São Paulo, Brazil - mota@ime.usp.br
We give a counting lemma for the number of copies of linear $k$-uniform connector-free hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs $G$. Let $H$ be a linear $k$-uniform connector-free hypergraph and let $G$ be a $k$-uniform hypergraph with $n$ vertices. Set $d_H=\max\{\delta(J)\colon J\subset H\}$ and $D_H=\min\{kd_H,\Delta(H)\}$. We proved that if the vertices of $G$ do not have large degree, small families of $(k-1)$-element sets of $V(G)$ do not have large common neighbourhood and most of the pairs of sets in ${V(G)\choose k-1}$ have the 'right' number of common neighbours, then the number of embeddings of $H$ in $G$ is $(1+o(1))n^{|V(H)|}p^{|E(H)|}$, given that $p\gg n^{-1/D_H}$ and $|E(G)|={n\choose k}p$. This generalizes a result by Kohayakawa, R\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo-random graphs, Israel J. Math. 139 (2004), 93-137], who proved that, for $p$ as above, this result holds for graphs, where $H$ is a triangle-free graph.
Joint work with Yoshiharu Kohayakawa, Mathias Schacht and Anusch Taraz.
Stability and Ramsey numbers for cycles and wheels
Nicolás Sanhueza
Universidad de Chile, Chile - nicolas@sanhueza.net
We study the structure of red-blue edge-colorings of a complete graph, in such a way that certain graphs don't appear as monochromatic subgraphs. More concretely, we consider the case of an odd positive integer $n$, and forbidden monochromatic graphs given by a red $n$-cycle $C_n$ and a blue $n$-wheel $W_n = C_n + K_1$.
Our main result is that if complete graph $G$ of appropriate size has a red-blue edge-coloring of its edges in a way such that $C_n$ is not a red subgraph of $G$ nor $W_n$ is a blue subgraph of $G$; then deleting at most two vertices we obtain a partition of the vertices of $G$ in three sets such that the edges with both ends in the same element of the partition are colored red, and blue otherwise.
We can see this result as a generalization of results previously shown by Nikiforov and Schelp, in the case where the forbidden monochromatic subgraphs are odd cycles.
As a secondary result of our proof, we obtain two bounds for the Ramsey number of $r(C_{2k+1},W_{2k+1})$: one is tighter for small values of $k$, and the other is better in the asymptotic case. The exact values for $r(C_{2k+1},W_{2k+1})$ are presently an open problem. Our bounds are a rough approximation to the conjectured values and show that they are, at least, asymptotically true.
Joint work with Maya Stein (Universidad de Chile, Chile).
Linear-time algorithms for neighborhood covering and independence on two superclasses of cographs
Xavier Sebastián Warnes
Universidad de Buenos Aires, Argentina - xwarnes@dc.uba.ar
Given a simple graph $G$, a set $C \subseteq V(G)$ is a neighborhood cover set if every edge and vertex of $G$ belongs to some $G[v]$ with $v \in C$, where $G[v]$ denotes the subgraph of $G$ induced by the closed neighborhood of the vertex $v$. Two elements of $E(G) \cup V(G)$ are neighborhood-independent if there is no vertex $v\in V(G)$ such that both elements are in $G[v]$. A set $S \subseteq V(G)\cup E(G)$ is said to be a neighborhood-independent set if every pair of elements of $S$ is neighborhood-independent. Let $\rho_{\mathrm n}(G)$ be the size of a minimum neighborhood cover set and $\alpha_{\mathrm n}(G)$ of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs as those where $\rho_{\mathrm n}(G') = \alpha_{\mathrm n}(G')$ for every induced subgraph $G'$ of $G$.\\
In this work we present linear-time algorithms for finding a minimum neighborhood cover set and a maximum neighborhood-independent set for two superclasses of cographs --- namely, $P_4$-tidy graphs and tree-cographs. We also give linear-time algorithms for recognizing neighborhood-perfect graphs within the same graph classes. These algorithms rely on the structure of the corresponding modular decomposition trees.
Joint work with Guillermo Durán (Universidad de Buenos Aires, Argentina) and Martín Safe (Universidad Nacional de General Sarmiento, Argentina).