Auswahl der wissenschaftlichen Literatur zum Thema „Bipartite Helly graphs“

Graphs and Algorithms International audience A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n2+αm) time and O(n+m) space. (Here n, m, and α= O(m1/2) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n+m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n2 + αm) time and O(αm) space.

AbstractGiven q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weaklyH-saturated in F if the edges in $$E(F)\setminus E(G)$$ E ( F ) \ E ( G ) admit an ordering $$e_1,\ldots , e_k$$ e 1 , … , e k so that for all $$i\in [k]$$ i ∈ [ k ] the hypergraph $$G\cup \{e_1,\ldots ,e_i\}$$ G ∪ { e 1 , … , e i } contains an isomorphic copy of H which in turn contains the edge $$e_i$$ e i . The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobás in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al.

The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.

Le problème du médian est un des problèmes les plus étudiés en théorie des espaces métriques. Nous l'étudions dans les graphes médians d'un point de vue algorithmique. Nous présentons un algorithme linéaire basé sur un calcul rapide des classes de parallélisme des arêtes (les Thêta-classes) via un parcours en largeur particulier (LexBFS). Nous donnons également un algorithme linéaire pour le problème du médian dans les l1-complexes cubiques des graphes médians et dans les structures d'évènements.Ensuite, nous présentons une caractérisation des graphes aux médians connexes dans la p-ième puissance Gp du graphe et donnons une méthode polynomiale pour vérifier si un graphe est un graphe aux médians Gp-connexes, étendant un résultat de Bandelt et Chepoi (cas p=1). Nous utilisons cette caractérisation pour montrer que certaines classes de graphes sont G2-connexes, comme les graphes de Helly bipartis et les graphes pontés. Nous travaillons également sur l'aspect axiomatique en étudiant l'ABC-problème, qui consiste à déterminer les graphes (nommés ABC-graphes) dans lesquels la fonction médian est l'unique fonction consensus respectant trois axiomes simples (A) Anonymat, (B) Intervalle (Betweeness) et (C) Cohérence. Nous montrons que les graphes modulaires aux médians G2-connexes sont des ABC-graphes et définissons de nouveaux axiomes pour caractériser la fonction médian dans d'autres classes de graphes, comme les graphes aux médians connexes. Nous prouvons également que les graphes respectant la propriété d'appariement (qui sont des ABC-graphes) est une sous-classe propre des graphes de Helly bipartis et étudions la complexité de la reconnaissance de ces graphes
The median problem is one of the most investigated problem in metric graph theory. We will start by studying this problem in median graphs. We present a linear time algorithm based on the majority rule which characterize the median in median graphs and on a fast computation of the parallelism classes of the edges (the \Theta-classes) via LexBFS which is a particular breadth first search algorithm.We also provide linear time algorithms to compute the median set in the l_1-cube complexes of median graphs and in event structures. Then, we provide a characterization of the graphs with connected medians in the pth power of the graph and provide a polynomial method to check if a graph is a G^p-connected median graph, extending a result of Bandelt and Chepoi (case p=1). We use this characterization to prove that some important graph classes in metric graph theory have G2-connected medians, such as bipartite Helly graphs and bridged graphs. We will also studied the axiomatic aspect of the median function by investigating the ABC-problem, which determine the graphs (named ABC-graphs) in which the median function is the only consensus function verifying three simples axioms (A) Anonymat, (B) Betweeness and (C) Consistency. We show that modular graphs with G2-connected medians are ABC-graphs and define new axioms allowing us to characterize the median function on some graph classes. For example the graphs with connected medians (including Helly graphs). We also show that a known class of ABC-graphs (graphs satisfying the pairing property) is a proper subclass of bipartite Helly graphs and we investigate their recognition

We present a series of results related to the structural properties of the bipartite graph class known as circular-arc bigraphs. We also propose the definition of a Helly circular-arc bigraph subclass, based on a concept known as bipartite-Helly, along with a few results related to its structural properties.