Cubic graphs without cut‐vertices having the same path layer matrix

The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1–4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut‐vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177–182, 2001     

Regular graphs having the same path layer matrix

The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all paths in G. Elements (i,j) in this matrix is the number of simple paths in G having initial vertex v, and length j. For every r ≥ 3, pairs of nonisomorphic r-regular graphs having the same path layer matrix are presented.     

Small regular graphs having the same path layer matrix*

The path layer matrix of graph G contains quantitative information about all paths in G. The entry (i,j) in this matrix is the number of simple paths in G having initial vertex i and length j. Some new upper bounds for r‐regular graphs with the same path layer matrix are presented for r=4, 5, 6. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 219–221, 2002; DOI 10.1002/jgt.10005     

Cubic vertices in planar hypohamiltonian graphs

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in J. Graph Theory [79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.     

Cubic graphs on twelve vertices and the line graph of a finite affine plane

It is shown by Rao and Rao that certain geometric properties characterize the line graph of a BIB design with parameters b, v, r, k, 1, provided r - 2k + 1 < 0. If r = k + 1, and $\text{k \#\&62; 2}$, a characterization of the line graph of a finite affine plane is obtained. If r - 2k + 1 = 0, the only possible value for k is 2 and consequently r = k + 1 resulting in the case of the line graph of a finite affine plane. It is shown here that if r = k + 1 and k = 2, there are exactly seven other non-isomorphic graphs with those properties which are not the line graph of a finite affine plane and these are the only cubic graphs on twelve vertices with no quadrilaterals.     

On Homotopy of connected graphs having the same degree function

Let denote the set of simple graphs having the degree function . It is known that any two graphs from are homotopic in the sense that one can be obtained from the other by a series of simple two-edge switches so that every intermediate graph is in . Let denote the set of simple graphs having at most k components. A natural question arises whether it is possible to extend the above homotopy result on the class , and in particular, whether it is possible to obtain a connected simple graph from another connected simple graph of the same degree function by a series of two edge switches preserving connectivity. In this paper we give an answer to this question. We also consider two-edge switches of a special type and single out some classes of graphs for which these special operations provide the corresponding homotopy between its members.     

On the extremal geometric–arithmetic graphs with fixed number of vertices having minimum degree

Annals of Operations Research - The geometric–arithmetic index GA of a graph is defined as sum of weights of all edges of graph. The weight of one edge is quotient of the geometric and...     

Permanents of graphs with cut vertices

In this article, we determine upper bounds for the permanent of the adjacency matrix of a graph with cut vertices in terms of the order of the graph and the number of its cut vertices.     

Permanents of graphs with cut vertices

In this article, we determine upper bounds for the permanent of the adjacency matrix of a graph with cut vertices in terms of the order of the graph and the number of its cut vertices.     

On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices.     

Ramsey numbers for graphs with five vertices

The Ramsey numbers r(F¹, F²) are tabulated for essentially all but six pairs of graphs F¹ and F² with five vertices.     

Domination dot-critical graphs with no critical vertices

A graph G is dot-critical if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. Burton and Sumner [Discrete Math. 306 (2006) 11-18] posed the problem: Is it true that for k?4, there exists a totally k-dot-critical graph with no critical vertices? In this paper, we show that this problem has a positive answer.     

Constructing graphs with pairs of pseudo-similar vertices

Vertices u and v in the graph G are said to be pseudo-similar if G ? u ? G ? v but no automorphism of G maps u onto v. It is shown that a known procedure for constructing finite graphs with pairs of pseudo-similar vertices actually produces all such graphs. An additional procedure for constructing infinite graphs with pseudo-similar vertices is introduced and it is shown that all such graphs can be obtained by using either this or the first-mentioned method. The corresponding result for pseudo-similar edges is given.     

Distance-biregular graphs with 2-valent vertices and distance-regular line graphs

A graph G is called distance-regularized if each vertex of G admits an intersection array. It is known that every distance-regularized graph is either distance-regular (DR) or distance-biregular (DBR). Note that DBR means that the graph is bipartite and the vertices in the same color class have the same intersection array. A (k, g)-graph is a k-regular graph with girth g and with the minimum possible number of vertices consistent with these properties. Biggs proved that, if the line graph L(G) is distance-transitive, then G is either K_1,n or a (k, g)-graph. This result is generalized to DR graphs by showing that the following are equivalent: (1) L(G) is DR and G ≠ K_1,n for n ≥ 2, (2) G and L(G) are both DR, (3) subdivision graph S(G) is DBR, and (4) G is a (k, g)-graph. This result is used to show that a graph S is a DBR graph with 2-valent vertices iff S = K_2,′ or S is the subdivision graph of a (k, g)-graph. Let G⁽²⁾ be the graph with vertex set that of G and two vertices adjacent if at distance two in G. It is shown that for a DBR graph G, G⁽²⁾ is two DR graphs. It is proved that a DR graph H without triangles can be obtained as a component of G⁽²⁾ if and only if it is a (k, g)-graph with g ≥ 4.     

Cubic graphs with most automorphisms

We give a sharp bound for the order of the automorphism group of a connected simple cubic graph on a given number of vertices. For each number of vertices we construct a graph, unique in special cases, attaining the bound. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 99–115, 2010     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Cataloguing the graphs on 10 vertices

We describe the production of a catalogue of all the nonisomorphic graphs on 10 vertices by means of a computer program. The basic program generated all the nonisomorphic graphs with a given degree sequence. Some tables, derived from the catalogue, concerning the numbers of automorphisms of these graphs are given at the end of the paper.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

Character degree graphs with no complete vertices

Let Γ be a graph in which each vertex is non-adjacent to another different one. We show that, if G is a finite solvable group with abelian Fitting subgroup and with character degree graph $\Gamma (G)=\Gamma$, then G is a direct product of subgroups having a disconnected character degree graph. In particular, Γ is a join of disconnected graphs. We deduce also that solvable groups with abelian Fitting subgroup have a character degree graph with diameter at most 2.