Page 1

Displaying 1 – 9 of 9

Showing per page

Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Sebastian M. Cioabă, Xiaofeng Gu (2016)

Czechoslovak Mathematical Journal

The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.

On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs

Július Czap, Jakub Przybyło, Erika Škrabuľáková (2016)

Discussiones Mathematicae Graph Theory

A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true...

Testing Cayley graph densities

Goulnara N. Arzhantseva, Victor S. Guba, Martin Lustig, Jean-Philippe Préaux (2008)

Annales mathématiques Blaise Pascal

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m -generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2 m . We test amenable and non-amenable...

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West (2014)

Discussiones Mathematicae Graph Theory

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...

Weak Saturation Numbers for Sparse Graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2013)

Discussiones Mathematicae Graph Theory

For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order...

Currently displaying 1 – 9 of 9

Page 1