Locally arc-transitive graphs of valence {3,4} with trivial edge kernel

In this paper, we consider connected locally G-arc-transitive graphs with vertices of valence 3 and 4, such that the kernel $G_{uv}^{[1]}$ of the action of an edge-stabiliser on the neighbourhood Γ(u)∪Γ(v) is trivial. We find 19 finitely presented groups with the property that any such group G is a quotient of one of these groups. As an application, we enumerate all connected locally arc-transitive graphs of valence {3,4} on at most 350 vertices whose automorphism group contains a locally arc-transitive subgroup G with $G_{uv}^{[1]} = 1$ .     

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.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

On Family of Graphs with Minimum Number of Spanning Trees

We show that there is a well-defined family of connected simple graphs Λ(n, m) on n vertices and m edges such that all graphs in Λ(n, m) have the same number of spanning trees, and if ${G \in \Lambda(n, m)}$ then the number of spanning trees in G is strictly less than the number of spanning trees in any other connected simple graph ${H, H \notin \Lambda(n, m)}$ , on n vertices and m edges.     

Invariant random graphs with iid degrees in a general geography

Let D be a non-negative integer-valued random variable and let G = (V, E) be an infinite transitive finite-degree graph. Continuing the work of Deijfen and Meester (Adv Appl Probab 38:287–298) and Deijfen and Jonasson (Electron Comm Probab 11:336–346), we seek an Aut(G)-invariant random graph model with V as vertex set, iid degrees distributed as D and finite mean connections (i.e., the sum of the edge lengths in the graph metric of G of a given vertex has finite expectation). It is shown that if G has either polynomial growth or rapid growth, then such a random graph model exists if and only if ${\mathbb{E}[D\,R(D)] < \infty}$ . Here R(n) is the smallest possible radius of a combinatorial ball containing more than n vertices. With rapid growth we mean that the number of vertices in a ball of radius n is of at least order exp(n ^c ) for some c > 0. All known transitive graphs have either polynomial or rapid growth. It is believed that no other growth rates are possible. When G has rapid growth, the result holds also when the degrees form an arbitrary invariant process. A counter-example shows that this is not the case when G grows polynomially. For this case, we provide other, quite sharp, conditions under which the stronger statement does and does not hold respectively. Our work simplifies and generalizes the results for ${G\,=\,\mathbb {Z}}$ in [4] and proves, e.g., that with ${G\,=\,\mathbb {Z}^d}$ , there exists an invariant model with finite mean connections if and only if ${\mathbb {E}[D^{(d+1)/d}] < \infty}$ . When G has exponential growth, e.g., when G is a regular tree, the condition becomes ${\mathbb {E}[D\,\log\,D] < \infty}$ .     

The reconstruction problem for certain infinite graphs

We are concerned with the notion of the degree-type (D _G ⁱ )_i∈ω of a graphG, whereD _G ⁱ is defined to be the number of vertices inG with degreei. In the first section the following results are proven:

1. IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD _G ⁱ andD _G ⁱ⁺¹ are both finite and different from 0, thenG is reconstructible.
2. Locally finite, countably infinite graphsG, for which infinitely manyD _G ⁱ are different from 0 but only finitely manyD _G ⁱ are infinite, are reconstructible.

In the second section we give some results about the reconstructibility of certain locally finite countably infinite interval graphs and show that a reconstruction of a planar, infinite graph has to be planar too.     

Treewidth computation and extremal combinatorics

For a given graph G and integers b,f ≥0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most $n\left( {_b^{b + f} } \right)$ such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G

1. compute the treewidth of G in time O(1.7549 ⁿ ) by making use of exponential space and in time O(2.6151 ⁿ ) and polynomial space
2. decide in time O(n ⁵· $_{k + 2}^{\left\lceil {(2n + k + 8)/3} \right\rceil } $ ) if the treewidth of G is at most k
3. list all minimal separators of G in time O(1.6181 ⁿ ) and all potential maximal cliques of G in time O(1.7549 ⁿ ).

This significantly improves previous algorithms for these problems.     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of  \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

Rainbow Connection Number, Bridges and Radius

Let G be a connected graph. The notion of rainbow connection number rc(G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85–98, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) proved that for every bridgeless graph G with radius r, ${rc(G)\leq r(r+2)}$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D ^r  = {u}, then G has r?1 connected dominating sets ${ D^{r-1}, D^{r-2},\ldots, D^{1}}$ such that ${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$ and ${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1\leq i \leq r}$ . From the result, we can get that if ${b_i\leq 2i+1}$ for all ${1\leq i\leq r}$ , then ${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1\leq i\leq r}$ , then ${rc(G)= \sum_{i=1}^{r}b_i}$ , the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the number of bridges in G.     

Bounds for the spectral abscissa of an element in a Banach algebra

For an arbitrary element x with spectrum sp(x) in a Banach algebra with identity e ≠ 0 we define the upper (lower) spectral abscissa \(\mathop {\sigma + (x)}\limits_{( - )} = \mathop {\max }\limits_{(\min )} \operatorname{Re} \lambda ,\lambda \in sp(x)\) . With the aid of the spectral radius \(\rho (x) = \mathop {\max }\limits_{\lambda \in sp(x)} \left| \lambda \right| = \mathop {\lim }\limits_{n \to + \infty } \parallel x^n {{1 - } \mathord{\left/ {\vphantom {{1 - } n}} \right. \kern-0em} n}\) we prove the following bounds: γ_?(x)?σ_?(x)?Γ_?(x)?₊(x)?σ₊(x)?γ₊(x), Γ_(±)(x)=(2δ_(±))^?1 (ρ _δ ² )_(±)?δ _(±) ² ?ρ ₀ ² )(δ_(±)≠0), γ_(±)(x)= (±)ρ_δ(±)?δ_(±), δ₊?0, δ_??0 ρ _(±) ^δ = ρ(x+eδ_(±)). We mention a case where equality is achieved, some corollaries,and discuss the sharpness of the bounds: for every ? > 0 there is a δ: ¦δ¦ ≥ρ ₀ ² /2?, such that Δ: = ¦γ_(±) x?Γ_(±) x¦?ε and conversely, if the bounds are computed for some δ ≠ 0, then △ ≤ρ ₀ ² /2 ¦δ¦. An example is considered.     

Contact Numbers for Congruent Sphere Packings in Euclidean 3-Space

The contact graph of an arbitrary finite packing of unit balls in Euclidean 3-space is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of a packing of n unit balls can have. Our method for finding lower and upper estimates for the largest contact numbers is a combination of analytic and combinatorial ideas and it is also based on some recent results on sphere packings. In particular, we prove that if C(n) denotes the largest number of touching pairs in a packing of n>1 congruent balls in Euclidean 3-space, then $0.695<\frac{6n-C(n)}{n^{\frac{2}{3}}}< \sqrt[3]{486}=7.862\dots$ for all $n=\frac{k(2k^{2}+1)}{3}$ with k??2.     

The Cyclomatic Number of a Graph and its Independence Polynomial at −1

If by s _k is denoted the number of independent sets of cardinality k in a graph G, then ${I(G;x)=s_{0}+s_{1}x+\cdots+s_{\alpha}x^{\alpha}}$ is the independence polynomial of G (Gutman and Harary in Utilitas Mathematica 24:97–106, 1983), where α = α(G) is the size of a maximum independent set. The inequality |I (G; ?1)| ≤ 2 ^ν(G), where ν(G) is the cyclomatic number of G, is due to (Engström in Eur. J. Comb. 30:429–438, 2009) and (Levit and Mandrescu in Discret. Math. 311:1204–1206, 2011). For ν(G) ≤ 1 it means that ${I(G;-1)\in\{-2,-1,0,1,2\}.}$ In this paper we prove that if G is a unicyclic well-covered graph different from C ₃, then ${I(G;-1)\in\{-1,0,1\},}$ while if G is a connected well-covered graph of girth ≥ 6, non-isomorphic to C ₇ or K ₂ (e.g., every well-covered tree ≠ K ₂), then I (G; ?1) = 0. Further, we demonstrate that the bounds {?2 ^ν(G), 2 ^ν(G)} are sharp for I (G; ?1), and investigate other values of I (G; ?1) belonging to the interval [?2 ^ν(G), 2 ^ν(G)].     

Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc(G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus–Gaddum-type result for the rainbow connection number. We prove that if G and ${\overline{G}}$ are both connected, then ${4\leq rc(G)+rc(\overline{G})\leq n+2}$ . Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively.     

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.     

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) ≤ 2r(G) + c, where r(G) denotes the radius of G and \({c \in \{0, 1, 2\}}\) . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time \({(2 + \frac{2}{r(G)})}\) -factor approximation algorithms.     

Iteratedk-line graphs

For integersk≥2, thek-line graph L_k(G) of a graph G is defined as a graph whose vertices correspond to the complete subgraphs onk vertices in G with two distinct vertices adjacent if the corresponding complete subgraphs have 1 common vertices inG. We define iteratedk-line graphs byL _k ⁿ (G) ?L _k (L _k ^n?1 (G), whereL _k ⁰ (G) ?G. In this paper the iterated behavior of thek-line graph operator is investigated. It turns out that the behavior is quite different fork = 2 (the well-known line graph case),k = 3, and k≥4.     

Some Graphs with Double Domination Subdivision Number Three

A subset ${S \subseteq V(G)}$ is a double dominating set of G if S dominates every vertex of G at least twice. The double domination number dd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision number sd _dd (G) is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the double domination number. Atapour et al. (Discret Appl Math, 155:1700–1707, 2007) posed an open problem: Prove or disprove: let G be a connected graph with no isolated vertices, then 1 ≤ sd _dd (G) ≤ 2. In this paper, we disprove the problem by constructing some connected graphs with no isolated vertices and double domination subdivision number three.     

The generating graph of some monolithic groups

For a finite group G let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. We look for conditions on the positive integer m that ensure that Γ(G) contains a Hamiltonian cycle when G=S?Cm is the wreath product of a finite simple group S and a cyclic group of order m.     

Binary Labeling of Graphs

Let G = (V, E) be a graph. A mapping f: E(G) → {0, l} ^m is called a mod 2 coding of G, if the induced mapping g: V(G) → {0, l} ^m , defined as \(g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}\) , assigns different vectors to the vertices of G. Note that all summations are mod 2. Let m(G) be the smallest number m for which a mod 2 coding of G is possible. Trivially, m(G) ≥ ?Log₂ |V|?. Recently, Aigner and Triesch proved that m(G) ≤ ?Log₂ |V|? + 4. In this paper, we determine m(G). More specifically, we prove that if each component of G has at least three vertices, then $$mG = \left\{ {\begin{array}{*{20}c} {k,} & {if \left| V \right| \ne 2^k - 2} \\ {k + 1,} & {else} \\ \end{array} ,} \right.$$ where k = ?Log₂ |V|?.     

Shintani lifting and real-valued characters

We study Shintani lifting of real-valued irreducible characters of finite reductive groups. In particular, if G is a connected reductive group defined over ${\mathbb{F}_q}$ , and ψ is an irreducible character of G( ${\mathbb{F}_{q^m}}$ ) which is the lift of an irreducible character χ of G( ${\mathbb{F}_q}$ ), we prove ψ is real-valued if and only if χ is real-valued. In the case m = 2, we show that if χ is invariant under the twisting operator of G( ${\mathbb{F}_{q^2}}$ ), and is a real-valued irreducible character in the image of lifting from G( ${\mathbb{F}_q}$ ), then χ must be an orthogonal character. We also study properties of the Frobenius–Schur indicator under Shintani lifting of regular, semisimple, and irreducible Deligne–Lusztig characters of finite reductive groups.