On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

Equidistribution of Random Walks on Spheres

We study the equidistribution on spheres of the n-step transition probabilities of random walks on graphs. We give sufficient conditions for this property being satisfied and for the weaker property of asymptotical equidistribution. We analyze the asymptotical behaviour of the Green function of the simple random walk on ² and we provide a class of random walks on Cayley graphs of groups, whose transition probabilities are not even asymptotically equidistributed.     

Phase diagram of the Ising Model on a Cayley tree in the presence of competing interactions and magnetic field

We study the phase diagram for the Ising Model on a Cayley tree with competing nearest-neighbor interactionsJ ₁ and next-nearest-neighbor interactionsJ ₂ andJ ₃ in the presence of an external magnetic field. To perform this study, an iterative scheme similar to that appearing in real space renormalization group frameworks is established; it recovers, as particular cases, previous works by Vannimenus and by Inawashiroet al. At vanishing temperature, the phase diagram is fully determined, for all values and signs ofJ ₂/J ₁ andJ ₃/J ₂; in particular, we verify that values ofJ ₃/J ₂ high enough favor the paramagnetic phase. At finite temperatures, several interesting features (evolution of reentrances, separation of the modulated region into two disconnected pieces, etc.) are exhibited for typical values ofJ ₂/J ₁ andJ ₃/J ₂.Partially supported by the Brazilian Agencies CNPq and FINEP.     

Maximum flow problem on dynamic generative network flows with time-varying bounds

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

There is no (95, 40, 12, 20) strongly regular graph

We show that there is no (95, 40, 12, 20) strongly regular graph and, consequently, there is no (96, 45, 24, 18) strongly regular graph, no nontrivial regular two‐graph on 96 vertices, and no partial geometry pg(4, 9, 2). The main idea of the result is based on the star complement technique and requires a moderate amount of computation.     

Cayley digraphs and lexicographic product

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.      

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

一类退化椭圆型方程边值问题的适定性

研究一类特殊退化椭圆型方程边值问题的适定性,该类问题与双曲空间中的极小图的Dirichlet问题,曲面的无穷小等距形变刚性问题等等的研究密切相关,而这类方程的特征形式在区域上是变号的,其适定性是值得深入讨论的.最后,得到这类边值问题的H~1弱解的存在性和唯一性.