Cubic vertex-transitive non-Cayley graphs of order 12<Emphasis Type="Italic">p</Emphasis>

A graph is said to be vertex-transitive non-Cayley if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order 12p, where p is a prime, is given. As a result, there are 11 sporadic and one infinite family of such graphs, of which the sporadic ones occur when p equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1 (mod 4), and in this family there is a unique graph for a given order.     

Finite edge-transitive oriented graphs of valency four with cyclic normal quotients

We study finite four-valent graphs \(\Gamma \) admitting an edge-transitive group G of automorphisms such that G determines and preserves an edge-orientation on \(\Gamma \), and such that at least one G-normal quotient is a cycle (a quotient modulo the orbits of a normal subgroup of G). We show, on the one hand, that the number of distinct cyclic G-normal quotients can be unboundedly large. On the other hand, existence of independent cyclic G-normal quotients (that is, they are not extendable to a common cyclic G-normal quotient) places severe restrictions on the graph \(\Gamma \) and we classify all examples. We show there are five infinite families of such pairs \((\Gamma ,G)\) and in particular that all such graphs have at least one normal quotient which is an unoriented cycle. We compare this new approach with existing treatments for the sub-class of weak metacirculant graphs with these properties, finding that only two infinite families of examples occur in common from both analyses. Several open problems are posed.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

Unicyclic nonintegral sum graphs

A graph G = (V,E) is an integral sum graph if there exists a labeling S(G) ? Z such that V = S(G) and every two distinct vertices u, υ ∈ V are adjacent if and only if u + υ ∈ V. A connected graph G = (V,E) is called unicyclic if |V| = |E|. In this paper two infinite series are constructed of unicyclic graphs that are not integral sum graphs.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Unicyclic graphs with bicyclic inverses

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)^?1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.     

Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

Tetravalent Vertex-Transitive Graphs of Order Twice A Prime Square

A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, a complete classification is given of tetravalent vertex-transitive non-Cayley graphs of order \(2p^2\) for any prime p.     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

Token Graphs

For a graph G and integer k ≥ 1, we define the token graph F _k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F _k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F _k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.     

Group distance magic and antimagic graphs

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups.     

Super Edge-connectivity and Zeroth-order General Randić Index for −1 ≤ <Emphasis Type="Italic">α</Emphasis> &lt; 0

Let G be a connected graph with order n, minimum degree δ = δ(G) and edge-connectivity λ = λ(G). A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randi? index \(R_\alpha ^0\left( G \right) = \sum\limits_{x \in V\left( G \right)} {d_G^\alpha \left( x \right)} \), where d_G(x) denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randi? index for ?1 ≤ α < 0, respectively.     

Atomic subspaces of {L_1}-martingale spaces

In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G is representable with S if it is possible to attach rational numbers to the vertices of G such that the vertices v₁, v₂ are connected by an edge if and only if the difference of the attached values is an S-unit. In Part I we gave several results concerning the representability of graphs in the above sense.     

On linkedness in the Cartesian product of graphs

We study linkedness of the Cartesian product of graphs and prove that the product of an a-linked and a b-linked graph is \((a+b-1)\)-linked if the graphs are sufficiently large. Further bounds in terms of connectivity are shown. We determine linkedness of products of paths and products of cycles.     

Generalized 3-edge-connectivity of Cartesian product graphs

The generalized k-connectivity κ _k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ _k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T ₁, T ₂, …, T _l in G such that S ? V (T _i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ ₃(G □ H) ? λ ₃(G) + λ ₃(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.     

Strictly Deza line graphs

For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.     

Graphs with small total rainbow connection number

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that \({\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}}{n - 1} \\2\end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}}n \\2\end{array}} \right) - 1\), and \({\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}}{n - 2} \\2\end{array}} \right) + 2\). Next, we investigate the total rainbow connection numbers of graphs G with |V(G)| = n, diam(G) ≥ 2, and clique number ω(G) = n ? s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.     

Valency seven symmetric graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, all connected valency seven symmetric graphs of order 2pq are classified, where p, q are distinct primes. It follows from the classification that there is a unique connected valency seven symmetric graph of order 4p, and that for odd primes p and q, there is an infinite family of connected valency seven one-regular graphs of order 2pq with solvable automorphism groups, and there are four sporadic ones with nonsolvable automorphism groups, which is 1, 2, 3-arc transitive, respectively. In particular, one of the four sporadic ones is primitive, and the other two of the four sporadic ones are bi-primitive.     

2-Connected factor-critical graphs <Emphasis Type="Italic">G</Emphasis> with exactly |<Emphasis Type="Italic">E</Emphasis>(<Emphasis Type="Italic">G</Emphasis>)| + 1 maximum matchings

A connected graph G is said to be a factor-critical graph if G ?v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly |E(G)| + 1 maximum matchings is characterized.