Displaying 521 – 540 of 849

Showing per page

The set chromatic number of a graph

Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)

Discussiones Mathematicae Graph Theory

For a nontrivial connected graph G, let c: V(G)→ N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u,v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs are determined...

The signed matchings in graphs

Changping Wang (2008)

Discussiones Mathematicae Graph Theory

Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → -1,1 satisfying e E G ( v ) x ( e ) 1 for every v ∈ V(G), where E G ( v ) = u v E ( G ) | u V ( G ) . The maximum of the values of e E ( G ) x ( e ) , taken over all signed matchings x, is called the signed matching number and is denoted by β’₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β’₁(G) for general graphs....

The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices

Muhuo Liu, Xuezhong Tan, Bo Lian Liu (2010)

Czechoslovak Mathematical Journal

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with n vertices and k pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with n vertices and k pendant vertices, respectively....

The size of minimum 3-trees: cases 0 and 1 mod 12

Jorge L. Arocha, Joaquín Tey (2003)

Discussiones Mathematicae Graph Theory

A 3-uniform hypergraph is called a minimum 3-tree, if for any 3-coloring of its vertex set there is a heterochromatic triple and the hypergraph has the minimum possible number of triples. There is a conjecture that the number of triples in such 3-tree is ⎡(n(n-2))/3⎤ for any number of vertices n. Here we give a proof of this conjecture for any n ≡ 0,1 mod 12.

The sizes of components in random circle graphs

Ramin Imany-Nabiyyi (2008)

Discussiones Mathematicae Graph Theory

We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure of random...

The skeleta of convex bodies

David G. Larman (2009)

Banach Center Publications

The connectivity and measure theoretic properties of the skeleta of convex bodies in Euclidean space are discussed, together with some long standing problems and recent results.

The small Ree group 2 G 2 ( 3 2 n + 1 ) and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Let G be a finite group. The main supergraph 𝒮 ( G ) is a graph with vertex set G in which two vertices x and y are adjacent if and only if o ( x ) o ( y ) or o ( y ) o ( x ) . In this paper, we will show that G 2 G 2 ( 3 2 n + 1 ) if and only if 𝒮 ( G ) 𝒮 ( 2 G 2 ( 3 2 n + 1 ) ) . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group 2 G 2 ( 3 2 n + 1 ) .

Currently displaying 521 – 540 of 849