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 376

Showing per page

Partitions of networks that are robust to vertex permutation dynamics

Gary Froyland, Eric Kwok (2015)

Special Matrices

Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex...

Partitions of some planar graphs into two linear forests

Piotr Borowiecki, Mariusz Hałuszczak (1997)

Discussiones Mathematicae Graph Theory

A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...

Partitions sans petites parts (II)

Élie Mosaki (2008)

Journal de Théorie des Nombres de Bordeaux

On désigne par r ( n , m ) le nombre de partitions de l’entier n en parts supérieures ou égales à m , et R ( n , m ) = r ( n - m , m ) le nombre de partitions de n de plus petite part m . Dans un précédent article (voir [9]) un développement asymptotique de r ( n , m ) est obtenu uniformément pour 1 ≤ m = O ( n )  ; on complète ce développement uniformément pour 1 ≤ m = ( n log - 3 n ) . Afin de prolonger les résultats jusqu’à m ≤ n , on donne un encadrement de r ( n , m ) valable pour n 2 / 3 ≤ m ≤ n en utilisant la relation r ( n , m ) = ∑ t = 1 ⌊ n / m ⌋ P ( n - ( m - 1 ) t , t ) où P ( i , t ) désigne le nombre de partitions de i en exactement t parts. On donne aussi une...

Path and cycle factors of cubic bipartite graphs

M. Kano, Changwoo Lee, Kazuhiro Suzuki (2008)

Discussiones Mathematicae Graph Theory

For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

Currently displaying 101 – 120 of 376