Irreducible pseudo 2-factor isomorphic cubic bipartite graphs

A bipartite graph is pseudo 2-factor isomorphic if the number of circuits in each 2-factor of the graph is always even or always odd. We proved (Abreu et?al., J Comb Theory B 98:432–442, 2008) that the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graph of girth 4 is K _3,3, and conjectured (Abreu et?al., 2008, Conjecture 3.6) that the only essentially 4-edge-connected cubic bipartite graphs are K _3,3, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations n ₃ due to Martinetti (1886) in which all symmetric configurations n ₃ can be obtained from an infinite set of so called irreducible configurations (Martinetti, Annali di Matematica Pura ed Applicata II 15:1–26, 1888). The list of irreducible configurations has been completed by Boben (Discret Math 307:331–344, 2007) in terms of their irreducible Levi graphs. In this paper we characterize irreducible pseudo 2-factor isomorphic cubic bipartite graphs proving that the only pseudo 2-factor isomorphic irreducible Levi graphs are the Heawood and Pappus graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.     

Intersection Dimensions of Graph Classes

The intersection dimension of a graphG with respect to a classA of graphs is the minimumk such thatG is the intersection of at mostk graphs on vertex setV(G) each of which belongs toA. We consider the question when the intersection dimension of a certain family of graphs is bounded or unbounded. Our main results are (1) ifA is hereditary, i.e., closed on induced subgraphs, then the intersection dimension of all graphs with respect toA is unbounded, and (2) the intersection dimension of planar graphs with respect to the class of permutation graphs is bounded. We also give a simple argument based on [Ben-Arroyo Hartman, I., Newman, I., Ziv, R.:On grid intersection graphs, Discrete Math.87 (1991) 41-52] why the boxicity (i.e., the intersection dimension with respect to the class of interval graphs) of planar graphs is bounded. Further we study the relationships between intersection dimensions with respect to different classes of graphs.     

Assouad-Nagata dimension of locally finite groups and asymptotic cones

In this paper we study two problems concerning Assouad-Nagata dimension:

(1)

Is there a metric space of positive asymptotic Assouad-Nagata dimension such that all of its asymptotic cones are of Assouad-Nagata dimension zero? (Dydak and Higes, 2008 [11, Question 4.5]).

(2)

Suppose G is a locally finite group with a proper left invariant metric dG. If dimAN(G,dG)>0, is dimAN(G,dG) infinite? (Brodskiy et al., preprint [6, Problem 5.3]).

The first question is answered positively. We provide examples of metric spaces of positive (even infinite) Assouad-Nagata dimension such that all of its asymptotic cones are ultrametric. The metric spaces can be groups with proper left invariant metrics.The second question has a negative solution. We show that for each n there exists a locally finite group of Assouad-Nagata dimension n. As a consequence this solves for non-finitely generated countable groups the question about the existence of metric spaces of finite asymptotic dimension whose asymptotic Assouad-Nagata dimension is larger but finite.     

On the metric dimension of HDN

The concept of metric basis is useful for robot navigation. In graph G, a robot is aware of its current location by sending signals to obtain the distances between itself and the landmarks in G. Its position is determined uniquely in G if it knows its distances to sufficiently many landmarks. The metric basis of G is defined as the minimum set of landmarks such that all other vertices in G can be uniquely determined and the metric dimension of G is defined as the cardinality of the minimum set of landmarks. The major contribution of this paper is that we have partly solved the open problem proposed by Manuel et al. [9], by proving that the metric dimension of $\text{HDN1}(n)$ and $\text{HDN2}(n)$ are either 3 or 4. However, the problem of finding the exact metric dimension of HDN networks is still open.     

The geometry of graphs and some of its algorithmic applications

In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images. In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include:

1. A simple, unified approach to a number of problems on multicommodity flows, including the Leighton-Rao Theorem [37] and some of its extensions. We solve an open question in this area, showing that the max-flow vs. min-cut gap in thek-commodities problem isO(logk). Our new deterministic polynomial-time algorithm finds a (nearly tight) cut meeting this bound.
2. For graphs embeddable in low-dimensional spaces with a small distortion, we can find low-diameter decompositions (in the sense of [7] and [43]). The parameters of the decomposition depend only on the dimension and the distortion and not on the size of the graph.
3. In graphs embedded this way, small balancedseparators can be found efficiently.

Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6. Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12].     

The variety of unary semigroups with associate inverse subsemigroup

In Billhardt et al. (Semigroup Forum 79:101–118, 2009) the authors introduced the notion of an associate inverse subsemigroup of a regular semigroup, extending the concept of an associate subgroup of a regular semigroup, first presented in Blyth et al. (Glasg. Math. J. 36:163–171, 1994). The semigroups of these two classes admit axiomatic characterisations in terms of unary operations and can, therefore, be considered as unary semigroups. In this paper we introduce the notion of unary semigroup with associate inverse subsemigroup [with associate subgroup] and show that the classes of such unary semigroups form varieties.     

Graphes cubiques d'indice trois,graphes cubiques isochromatiques,graphes cubiques d'indice quatre

The process introduced by E. Johnson [Amer. Math. Monthly73 (1966), 52–55] for constructing connected cubic graphs can be modified so as to obtain restricted classes of cubic graphs, in particular, those defined by their chromatic number or their chromatic index. We construct here the graphs of chromatic number three and the graphs whose chromatic number is equal to its chromatic index (isochromatic graphs). We then give results about the construction of the class of graphs of chromatic index four, and in particular, we construct an infinite class of “snarks.”     

An analysis of some linear graph layout heuristics

The worst-case performances of some heuristics for the fixed linear crossing number problem (FLCNP) are analyzed. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal “node line” in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In FLCNP, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems Masuda et al., 1990. In this paper we show that for each of the heuristics described, there exist classes of n-vertex, m-edge graphs which force it to obtain a number of crossings which is a function of n or m when the optimal number is a small constant. This leaves open the problem of finding a heuristic with a constant error bound for the problem.     

On the Constant Metric Dimension of Generalized Petersen Graphs P（n, 4）

In this paper,we consider the family of generalized Petersen graphs P(n,4).We prove that the metric dimension of P(n,4) is 3 when n ≡ 0(mod 4),and is 4 when n = 4k + 3(k is even).For n ≡ 1,2(mod 4) and n = 4k + 3(k is odd),we prove that the metric dimension of P(n,4) is bounded above by 4.This shows that each graph of the family of generalized Petersen graphs P(n,4)has constant metric dimension.     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

On the calculation of the Dunkl-Williams constant of normed linear spaces

Recently, Jiménez-Melado et al. [Jiménez-Melado A., Llorens-Fuster E., Mazcuñán-Navarro E.M., The Dunkl-Williams constant, convexity, smoothness and normal structure, J. Math. Anal. Appl., 2008, 342(1), 298–310] defined the Dunkl-Williams constant DW(X) of a normed linear space X. In this paper we present some characterizations of this constant. As an application, we calculate DW(?₂-?_∞) in the Day-James space ?₂-?_∞.     

On countable-to-one maps

In this paper, it is proved that a space with a point-countable base is an open, countable-to-one image of a metric space, and a quotient, countable-to-one image of a metric space is characterized by a point-countable ℵ₀-weak base. Examples are provided in order to answer negatively questions posed by Gruenhage et al. [G. Gruenhage, E. Michael, Y. Tanaka, Spaces determined by point-countable covers, Pacific J. Math. 113 (1984) 303-332] and Tanaka [Y. Tanaka, Closed maps and symmetric spaces, Questions Answers Gen. Topology 11 (1993) 215-233].     

Remarks on Q-integral complete multipartite graphs

A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs.     

A Generalization of Strongly Regular Graphs

Motivated from an example of ridge graphs relating to metric polytopes, a class of connected regular graphs such that the squares of their adjacency matrices are in certain symmetric Bose-Mesner algebras of dimension 3 is considered in this paper as a generalization of strongly regular graphs. In addition to analysis of this prototype example defined over (MetP₅)^*, some general properties of these graphs are studied from the combinatorial view point.AMS Subject Classification: 05E30.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

Structural properties of graphs of diameter 2 with maximal repeats

It was shown using eigenvalue analysis by Erdös et al. that with the exception of C₄, there are no graphs of diameter 2, of maximum degree d and of order d², that is, one less than the Moore bound. These graphs belong to a class of regular graphs of diameter 2, and having certain interesting structural properties, which will be proved in this paper.