All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 6 Next

Displaying 101 – 120 of 662

Showing per page

Sharp bounds for the number of matchings in generalized-theta-graphs

Ardeshir Dolati, Somayyeh Golalizadeh (2012)

Discussiones Mathematicae Graph Theory

A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θⁿₖ. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.

Sharp edge-homotopy on spatial graphs.

Ryo Nikkuni (2005)

Revista Matemática Complutense

A sharp-move is known as an unknotting operation for knots. A self sharp-move is a sharp-move on a spatial graph where all strings in the move belong to the same spatial edge. We say that two spatial embeddings of a graph are sharp edge-homotopic if they are transformed into each other by self sharp-moves and ambient isotopies. We investigate how is the sharp edge-homotopy strong and classify all spatial theta curves completely up to sharp edge-homotopy. Moreover we mention a relationship between...

Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs

Yuefang Sun (2016)

Discussiones Mathematicae Graph Theory

The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. 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) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds...

Sharp Upper Bounds on the Signless Laplacian Spectral Radius of Strongly Connected Digraphs

Weige Xi, Ligong Wang (2016)

Discussiones Mathematicae Graph Theory

Let G = (V (G),E(G)) be a simple strongly connected digraph and q(G) be the signless Laplacian spectral radius of G. For any vertex vi ∈ V (G), let d+i denote the outdegree of vi, m+i denote the average 2-outdegree of vi, and N+i denote the set of out-neighbors of vi. In this paper, we prove that: (1) (1) q(G) = d+1 +d+2 , (d+1 ≠ d+2) if and only if G is a star digraph [...] ,where d+1, d+2 are the maximum and the second maximum outdegree, respectively [...] is the digraph on n vertices obtained...

Short cycles of low weight in normal plane maps with minimum degree 5

Oleg V. Borodin, Douglas R. Woodall (1998)

Discussiones Mathematicae Graph Theory

In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with w ( K 1 , 4 ) ≤ 30 . These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.

Short paths in 3-uniform quasi-random hypergraphs

Joanna Polcyn (2004)

Discussiones Mathematicae Graph Theory

Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms...

Currently displaying 101 – 120 of 662