Directed graphs over topological spaces: Some set theoretical aspects

In this paper we shall consider problems of the following type. SupposeG is some set,U is some family of subsests ofG (e.g.G could be the Euclidean plane andU might be the family of all sets of Lebesgue measure zero), andG is any directed graph overG (i.e. any collection of ordered pairs of members ofG) such that for eachg∈G the set {h:<g,h>∈G} belongs to the familyU. How large a setSυG must there exist with the property that (S×S) ∩G=, i.e. such that it is totally disconnected? In many of the cases we shall consider (including the particular example above), the answer will turn out to be independent of the axioms of set theory and will remain so even after adjoining the negation of the continuum hypothesis.     

Distinguishing-Transversal in Hypergraphs and Identifying Open Codes in Cubic Graphs

The open neighborhood N(v) of a vertex v in a graph G is the set of vertices adjacent to v in G. A graph is twin-free (or open identifiable) if every two distinct vertices have distinct open neighborhoods. A separating open code in G is a set C of vertices such that \({N(u) \cap C \neq N(v) \cap C}\) for all distinct vertices u and v in G. An open dominating set, or total dominating set, in G is a set C of vertices such that \({N(u) \cap C \ne N(v) \cap C}\) for all vertices v in G. An identifying open code of G is a set C that is both a separating open code and an open dominating set. A graph has an identifying open code if and only if it is twin-free. If G is twin-free, we denote by \({\gamma^{\rm IOC}(G)}\) the minimum cardinality of an identifying open code in G. A hypergraph H is identifiable if every two edges in H are distinct. A distinguishing-transversal T in an identifiable hypergraph H is a subset T of vertices in H that has a nonempty intersection with every edge of H (that is, T is a transversal in H) such that T distinguishes the edges, that is, \({e \cap T \neq f \cap T}\) for every two distinct edges e and f in H. The distinguishing-transversal number \({\tau_D(H)}\) of H is the minimum size of a distinguishing-transversal in H. We show that if H is a 3-uniform identifiable hypergraph of order n and size m with maximum degree at most 3, then \({20\tau_D(H) \leq 12n + 3m}\) . Using this result, we then show that if G is a twin-free cubic graph on n vertices, then \({\gamma^{\rm IOC}(G) \leq 3n/4}\) . This bound is achieved, for example, by the hypercube.     

Upper Bounds on the Paired Domination Subdivision Number of a Graph

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number ${{\rm sd}_{\gamma _{\rm pr}}(G)}$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then ${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$ . We also characterize trees T such that ${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$ .     

Simple exceptional groups of Lie type are determined by their character degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let ${{\rm cd}(G)=\{\chi(1)\;|\;\chi\in {\rm Irr}(G)\}}$ be the set of all irreducible complex character degrees of G forgetting multiplicities, and let X₁(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be any non-abelian simple exceptional group of Lie type. In this paper, we will show that if S is a non-abelian simple group and ${{\rm cd}(S)\subseteq {\rm cd}(H)}$ then S must be isomorphic to H. As a consequence, we show that if G is a finite group with ${{\rm X}_1(G)\subseteq {\rm X}_1(H)}$ then G is isomorphic to H. In particular, this implies that the simple exceptional groups of Lie type are uniquely determined by the structure of their complex group algebras.     

Ehrhart Series for Connected Simple Graphs

The Ehrhart ring of the edge polytope ${\mathcal{P}_G}$ for a connected simple graph G is known to coincide with the edge ring of the same graph if G satisfies the odd cycle condition. This paper gives for a graph which does not satisfy the condition, a generating set of the defining ideal of the Ehrhart ring of the edge polytope, described by combinatorial information of the graph. From this result, two factoring properties of the Ehrhart series are obtained; the first one factors out bipartite biconnected components, and the second one factors out a even cycle which shares only one edge with other part of the graph. As an application of the factoring properties, the root distribution of Ehrhart polynomials for bipartite polygon trees is determined.     

Splitter Theorems for 4-Regular Graphs

Let ${\Phi_{k,g}}$ be the class of all k-edge connected 4-regular graphs with girth of at least g. For several choices of k and g, we determine a set ${\mathcal{O}_{k,g}}$ of graph operations, for which, if G and H are graphs in ${\Phi_{k,g}}$ , G ≠ H, and G contains H as an immersion, then some operation in ${\mathcal{O}_{k,g}}$ can be applied to G to result in a smaller graph G′ in ${\Phi_{k,g}}$ such that, on one hand, G′ is immersed in G, and on the other hand, G′ contains H as an immersion.     

Random mappings of scaled graphs

Given a connected finite graph Γ with a fixed base point O and some graph G with a based point we study random 1-Lipschitz maps of a scaled Γ into G. We are mostly interested in the case where G is a Cayley graph of some finitely generated group, where the construction does not depend on the choice of base points. A particular case of Γ being a graph on two vertices and one edge corresponds to the random walk on G, and the case where Γ is a graph on two vertices and two edges joining them corresponds to Brownian bridge in G. We show, that unlike in the case ${G=\mathbb Z^d}$ , the asymptotic behavior of a random scaled mapping of Γ into G may differ significantly from the asymptotic behavior of random walks or random loops in G. In particular, we show that this occurs when G is a free non-Abelian group. Also we consider the case when G is a wreath product of ${\mathbb Z}$ with a finite group. To treat this case we prove new estimates for transition probabilities in such wreath products. For any group G generated by a finite set S we define a functor E from category of finite connected graphs to the category of equivalence relations on such graphs. Given a finite connected graph Γ, the value E _G,S (Γ) can be viewed as an asymptotic invariant of G.     

On Cartesian Product of Factor-Critical Graphs

A graph G is k-factor-critical if G ? S has a perfect matching for any k-subset S of V(G). In this paper, we investigate the factor-criticality in Cartesian products of graphs and show that Cartesian product of an m-factor-critical graph and an n-factor-critical graph is ${(m+n+\varepsilon )}$ -factor-critical, where ${\varepsilon = 0}$ if both of m and n are even; ${\varepsilon = 1}$ , otherwise. Moreover, this result is best possible.     

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of 2-edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every 2-edge-colored graph can be partitioned into at most 2α(G) monochromatic cycles, where α(G) denotes the independence number of G. Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from o(|V (G)|) vertices, the vertex set of any 2-edge-colored graph G with minimum degree at least \(\tfrac{{(1 + \varepsilon )3|V(G)|}} {4}\) can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that \(\bar G\) does not contain a fixed bipartite graph H, we show that in every 2-edge-coloring of G, |V (G)| ? c(H) vertices can be covered by two vertex disjoint paths of different colors, where c(H) is a constant depending only on H. In particular, we prove that c(C ₄)=1, which is best possible.     

An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of ${V {\setminus} S}$ is adjacent to a vertex in ${V {\setminus} S}$ . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ _tr(G) of G. Jiang et?al. (Graphs Combin 25:341–350, 2009) showed that if G is a connected cubic graph of order n, then γ _tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ _tr(G) ≤ (n?+?4)/2. We provide two infinite families of connected cubic graphs G with γ _tr(G) = n/2, showing that our new improved bound is essentially best possible.     

A Classification of Graphs Whose Subdivision Graph is Locally Distance Transitive

The subdivision graph S(Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for s ≤ 2 diam(Σ) ? 1 and some G?≤ Aut(Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for some s?≥ 2 diam(Σ) and some G?≤ Aut(Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive.     

Arc-transitive Dihedrants of Odd Prime-power Order

Let G be a finite group with identity element 1, and S be a subset of G such that ${1 \notin S}$ and S = S ^?1. The Cayley graph Cay(G, S) has vertex set G, and x, y in G are adjacent if and only if ${xy^{-1} \in S}$ . In this paper we classify the connected, arc-transitive Cayley graphs ${{\rm Cay}(D_{2p^n}, S),}$ where ${D_{2p^n}}$ is the dihedral group of order 2p ⁿ , p is an odd prime.     

Flat bundles on G/Γ and stability

Let G be a connected complex Lie group and Γ a cocompact lattice in G. Let H be a connected reductive complex affine algebraic group and \({\rho\, : \Gamma\, \longrightarrow H}\) a homomorphism such that \({\rho(\Gamma)}\) is not contained in some proper parabolic subgroup of H. Let \({E^\rho_H}\) be the holomorphic principal H–bundle on G/Γ associated to ρ. We prove that \({E^\rho_H}\) is polystable. If ρ satisfies the further condition that \({\rho(\Gamma)}\) is contained in a compact subgroup of H, then we prove that \({E^\rho_H}\) is stable.     

Plane Graphs with Maximum Degree 6 are Edge-face 8-colorable

A plane graph G is edge-face k-colorable if the elements of \({E(G) \cup F(G)}\) can be colored with k colors so that any two adjacent or incident elements receive different colors. Sanders and Zhao conjectured that every plane graph with maximum degree Δ is edge-face (Δ +  2)-colorable and left the cases \({\Delta \in \{4, 5, 6\}}\) unsolved. In this paper, we settle the case Δ =  6. More precisely, we prove that every plane graph with maximum degree 6 is edge-face 8-colorable.     

An Upper Bound for the Total Restrained Domination Number of Graphs

Let G be a graph with vertex set V. A set ${D \subseteq V}$ is a total restrained dominating set of G if every vertex in V has a neighbor in D and every vertex in ${V \setminus D}$ has a neighbor in ${V \setminus D}$ . The minimum cardinality of a total restrained dominating set of G is called the total restrained domination number of G, and is denoted by γ _tr (G). In this paper, we prove that if G is a connected graph of order n ≥ 4 and minimum degree at least two, then ${\gamma_{tr}(G) \leq n-\sqrt[3]{n \over 4}}$ .     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

On the Edge Connectivity of Direct Products with Dense Graphs

Let ${\kappa^{\prime}(G)}$ be the edge connectivity of G and G × H the direct product of G and H. Let H be any graph with minimal degree ${\delta(H)>|V(H)|/2}$ . We prove that for any graph ${G, \kappa^{\prime}(G\times H)=\textup{min}\{2\kappa^{\prime}(G)|E(H)|,\delta(G)\delta(H)\}}$ . In addition, the structure of minimum edge cuts is described. As an application, we present a necessary and sufficient condition for G × K _n (n ≥ 3) to be super edge connected.     

Forbidden Induced Subgraphs for Perfect Matchings

Let ${\mathcal{F}}$ be a family of connected graphs. A graph G is said to be ${\mathcal{F}}$ -free if G is H-free for every graph H in ${\mathcal{F}}$ . We study the problem of characterizing the families of graphs ${\mathcal{F}}$ such that every large enough connected ${\mathcal{F}}$ -free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1–12, 2005), Fujita et al. (J Combin Theory Ser B 96(3):315–324, 2006) and Ota et al. (J Graph Theory, 67(3):250–259, 2011), where the authors were able to characterize such graph families ${\mathcal{F}}$ restricted to the cases ${|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}$ and ${|\mathcal{F}| \leq 3}$ , respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition ${|\mathcal{F}| \leq k}$ for some k ≥ 4.     

Quadrangulations on 3-Colored Point Sets with Steiner Points and Their Winding Numbers

Let P be a point set on the plane, and consider whether P is quadrangulatable, that is, whether there exists a 2-connected plane graph G with each edge a straight segment such that V(G) = P, that the outer cycle of G coincides with the convex hull Conv(P) of P, and that each finite face of G is quadrilateral. It is easy to see that it is possible if and only if an even number of points of P lie on Conv(P). Hence we give a k-coloring to P, and consider the same problem, avoiding edges joining two vertices of P with the same color. In this case, we always assume that the number of points of P lying on Conv(P) is even and that any two consecutive points on Conv(P) have distinct colors. However, for every k ≥ 2, there is a k-colored non-quadrangulatable point set P. So we introduce Steiner points, which can be put in any position of the interior of Conv(P) and each of which may be colored by any of the k colors. When k = 2, Alvarez et al. proved that if a point set P on the plane consists of \({\frac{n}{2}}\) red and \({\frac{n}{2}}\) blue points in general position, then adding Steiner points Q with \({|Q| \leq \lfloor \frac{n-2}{6} \rfloor + \lfloor \frac{n}{4} \rfloor +1}\) , P ∪ Q is quadrangulatable, but there exists a non-quadrangulatable 3-colored point set for which no matter how many Steiner points are added. In this paper, we define the winding number for a 3-colored point set P, and prove that a 3-colored point set P in general position with a finite set Q of Steiner points added is quadrangulatable if and only if the winding number of P is zero. When P ∪ Q is quadrangulatable, we prove \({|Q| \leq \frac{7n+34m-48}{18}}\) , where |P| = n and the number of points of P in Conv(P) is 2m.