Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Splits of circuits

This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem.If G is a graph and C is a circuit in G, we say that two circuits in G form a split of C if the symmetric difference of their edges sets is equal to the edge set of C, and if they are separated in G by the intersection of their vertex sets.García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952-4954, asked whether such a split exists for any circuit C whenever G is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs.     

Adjacency posets of planar graphs

In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poset has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

Revisiting a simple algorithm for the planar multiterminal cut problem

Yeh (2001) [W.-C. Yeh, A simple algorithm for the planar multiway cut problem, J. Algorithms 39 (2001) 68-77] described a simple algorithm with time complexity for the planar minimum k-terminal cut problem. In this paper, an example showing that the algorithm could fail to return a minimum k-cut is given.     

Er-doped silica–hafnia films for optical waveguides and spherical resonators

In this paper we present some result on sol–gel derived silica–hafnia systems. In particular we focus on fabrication, morphological and spectroscopic assessment of Er³⁺-activated thin films. Two examples of silica–hafnia-derived waveguiding glass ceramics, prepared by top–down and bottom–up techniques are reported, and the main optical properties are discussed. Finally, some properties of activated microspherical resonators, having a silica core, obtained by melting the end of a telecom fiber, coated with an Er³⁺-doped 70SiO₂–30HfO₂ film, are presented.     

Crystal Structure of Meso-tetrakis[4-(pentyloxy)phenyl]porphyrin

Abstract  The crystal structure of the title compound, C₆₄H₇₀N₄O₄, has been determined by single crystal X-ray diffraction methods. The title compound crystallizes in the monoclinic space group P2(1)/c with cell dimensions a = 13.8946(3) ?, b = 16.1069(3) ?, c = 12.1974(2) ?, β = 93.4050(10)°, Z = 2. The porphyrin core to be composed of four pyrrole rings linked through methane carbon bridges. Each molecule lies across a crystallographic inversion center. The porphyrin core is planar, which facilitates π-electron delocalization. The inner nitrogen H atoms are found localized on opposite pyrrole rings and these rings differ structurally from the other two pyrrole rings. The imino H atoms form bifurcated intramolecular hydrogen bonds with the adjacent unprotonated N atoms due to the contract porphyrin core. Graphical Abstract  The crystal structure of meso-tetrakis[4-(pentyloxy)phenyl]porphyrin is reported in this paper.