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 11 Next

Displaying 201 – 220 of 1226

Showing per page

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

A formula for all minors of the adjacency matrix and an application

R. B. Bapat, A. K. Lal, S. Pati (2014)

Special Matrices

We supply a combinatorial description of any minor of the adjacency matrix of a graph. This description is then used to give a formula for the determinant and inverse of the adjacency matrix, A(G), of a graph G, whenever A(G) is invertible, where G is formed by replacing the edges of a tree by path bundles.

A Gallai-type equality for the total domination number of a graph

Sanming Zhou (2004)

Discussiones Mathematicae Graph Theory

We prove the following Gallai-type equality γₜ(G) + εₜ(G) = p for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.

A game of composing binary relations

P. GoralČík, Z. Hedrlín, V. Koubek, J. Ryšunková (1982)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A general upper bound in extremal theory of sequences

Martin Klazar (1992)

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function f ( u , n ) which, for a given finite sequence u over k symbols, is defined as the maximum length m of a sequence v = a 1 a 2 . . . a m of integers such that 1) 1 ≤ a i ≤ n , 2) a i = a j , i ≠ j implies | i - j | ≥ k and 3) v contains no subsequence of the type u . We prove that f ( u , n ) is very near to be linear in n for any fixed u of length greater than 4, namely that f ( u , n ) = O ( n 2 O ( α ( n ) | u | - 4 ) ) . Here | u | is the length of u and α ( n ) is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

Currently displaying 201 – 220 of 1226