Page 1 Next

Displaying 1 – 20 of 5242

Showing per page

𝒟 n , r is not potentially nilpotent for n 4 r - 2

Yan Ling Shao, Yubin Gao, Wei Gao (2016)

Czechoslovak Mathematical Journal

An n × n sign pattern 𝒜 is said to be potentially nilpotent if there exists a nilpotent real matrix B with the same sign pattern as 𝒜 . Let 𝒟 n , r be an n × n sign pattern with 2 r n such that the superdiagonal and the ( n , n ) entries are positive, the ( i , 1 ) ( i = 1 ...

1-factors and characterization of reducible faces of plane elementary bipartite graphs

Andrej Taranenko, Aleksander Vesel (2012)

Discussiones Mathematicae Graph Theory

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...

1-slim triangles and uniform hyperbolicity for arc graphs and curve graphs

Sebastian Hensel, Piotr Przytycki, Richard C. H. Webb (2015)

Journal of the European Mathematical Society

We describe unicorn paths in the arc graph and show that they form 1-slim triangles and are invariant under taking subpaths. We deduce that all arc graphs are 7-hyperbolic. Considering the same paths in the arc and curve graph, this also shows that all curve graphs are 17-hyperbolic, including closed surfaces.

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Oleg V. Borodin, Anna O. Ivanova (2012)

Discussiones Mathematicae Graph Theory

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

2-factors in claw-free graphs

Guantao Chen, Jill R. Faudree, Ronald J. Gould, Akira Saito (2000)

Discussiones Mathematicae Graph Theory

We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced K 1 , 3 .) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such that v lies...

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

A complete 4-partite graph K m , m , m , m is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K m , m , m , m with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K m , m , m , m with four odd parts (i.e., the graphs K m , m , m , n and K m , m , n , n ) all d-halvable graphs are known as well, except for the graphs K m , m , n , n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K m , m , m , m with three or four different...

2-placement of (p,q)-trees

Beata Orchel (2003)

Discussiones Mathematicae Graph Theory

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which...

Currently displaying 1 – 20 of 5242

Page 1 Next