Journal of Graph Theory

Items from 1 to 11 out of 11 results

article

The number and average size of connected sets in graphs with degree constraints

John Haslegrave

Journal of Graph Theory > 100 > 3 > 530 - 542

The average size of connected vertex subsets of a connected graph generalises a much‐studied parameter for subtrees of trees. For trees, the possible values of this parameter are critically affected by the presence or absence of vertices of degree 2. We answer two questions of Andrew Vince regarding the effect of degree constraints on general connected graphs. We give a new lower bound, and the first...

article

Eigenvalues and $[a, b]$ ‐factors in regular graphs

Suil O

Journal of Graph Theory > 100 > 3 > 458 - 469

For positive integers,

r \geq 3

h \geq 1

, and

k \geq 1

, Bollobás, Saito, and Wormald proved some sufficient conditions for an

h

‐edge‐connected

r

‐regular graph to have a

k

‐factor in 1985. Lu gave an upper bound for the third largest eigenvalue in a connected

r

‐regular graph to have a

k

‐factor in 2010. Gu found an upper bound for certain eigenvalues in an

h

‐edge‐connected

r

‐regular graph to have a...

article

Counting hypergraphs with large girth

Sam Spiro, Jacques Verstraëte

Journal of Graph Theory > 100 > 3 > 543 - 558

Morris and Saxton used the method of containers to bound the number of

n

‐vertex graphs with

m

edges containing no

ℓ

‐cycles, and hence graphs of girth more than

ℓ

. We consider a generalization to

r

‐uniform hypergraphs. The girth of a hypergraph

H

is the minimum

ℓ \geq 2

such that there exist distinct vertices

v_{1}, …, v_{ℓ}

and hyperedges

e_{1}, …, e_{ℓ}

with

v_{i}, v_{i + 1} \in e_{i}

for all

1 \leq i

...

article

Monochromatic connected matchings in 2‐edge‐colored multipartite graphs

József Balogh, Alexandr Kostochka, Mikhail Lavrov, Xujun Liu

Journal of Graph Theory > 100 > 3 > 578 - 607

A matching

M

in a graph

G

is connected if all the edges of

M

are in the same component of

G

. Following Łuczak, there have been many results using the existence of large connected matchings in cluster graphs with respect to regular partitions of large graphs to show the existence of long paths and other structures in these graphs. We prove exact Ramsey‐type bounds on the...

article

On hamiltonian line graphs of hypergraphs

Xiaofeng Gu, Hong‐Jian Lai, Sulin Song

Journal of Graph Theory > 100 > 3 > 489 - 503

A graph is supereulerian if it has a spanning eulerian subgraph. Harary and Nash‐Williams in 1968 proved that the line graph of a graph

G

is hamiltonian if and only if

G

has a dominating eulerian subgraph, Jaeger in 1979 showed that every 4‐edge‐connected graph is supereulerian, and Catlin in 1988 proved that every graph with two edge‐disjoint spanning trees is a contractible configuration for supereulerianicity...

article

Issue Information

Journal of Graph Theory > 100 > 3 > 385 - 387

article

Strong chromatic index and Hadwiger number

Wouter Cames Batenburg, Rémi Joannis de Verclos, Ross J. Kang, François Pirot

Journal of Graph Theory > 100 > 3 > 435 - 457

We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each

k \geq 4

that any

K_{k}

‐minor‐free multigraph of maximum degree

Δ

has strong chromatic index at most

\frac{3}{2} (k - 2) Δ

. We present a construction certifying that if true the conjecture is asymptotically sharp as

Δ \to \infty

. In support of the conjecture,...

article

Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes

Yuansheng Yang, Guoqing Wang, Haoli Wang, Yan Zhou

Journal of Graph Theory > 100 > 3 > 389 - 434

Let

Q_{n}

be the

n

‐dimensional hypercube, and let

cr (Q_{n})

be the crossing number of

Q_{n}

. Erdős and Guy in 1973 conjectured the following equality:

cr (Q_{n}) = \frac{5}{32} 4^{n} - (\frac{n^{2} + 1}{2}) 2^{n - 2}

. In this paper, we construct a drawing of

Q_{n}

with less crossings when

n > 6

, which implies that for

n > 6

we have a strict inequality.

article

Asymptotically good edge correspondence colourings

Michael Molloy, Luke Postle

Journal of Graph Theory > 100 > 3 > 559 - 577

We prove that every simple graph with maximum degree

Δ

has edge correspondence number

Δ + o (Δ)

article

Radius, girth and minimum degree

Vojtĕch Dvorák, Peter Hintum, Amy Shaw, Marius Tiba

Journal of Graph Theory > 100 > 3 > 470 - 488

The objective of the present paper is to study the maximum radius

r

of a connected graph of order

n

, minimum degree

δ \geq 2

and girth at least

g \geq 4

. Erdős, Pach, Pollack and Tuza proved that if

g = 4

, that is, the graph is triangle‐free, then

r \leq \frac{n - 2}{δ} + 12

, and noted that up to the value of the additive constant, this upper bound is tight. In this paper we shall determine the exact maximum...

article

Recognizing interval bigraphs by forbidden patterns

Arash Rafiey

Journal of Graph Theory > 100 > 3 > 504 - 529

Let

H

be a connected bipartite graph with

n

vertices and

m

edges. We give an

O (n m)

time algorithm to decide whether

H

is an interval bigraph. The best known algorithm has time complexity

O (n m^{6} (m + n) \log n)

and it was developed by Muller in 1997. Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang in 2003. We transform the problem...

Filter options

Number:
3
Volume:
100

Publication date

Last 3 months (11)
Last year (11)
Last 3 years (11)

Close

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

From:

To:
Set your own date range

INFONA - science communication portal

Journal of Graph Theory

The number and average size of connected sets in graphs with degree constraints

Eigenvalues and $[a, b]$ ‐factors in regular graphs

Counting hypergraphs with large girth

Monochromatic connected matchings in 2‐edge‐colored multipartite graphs

On hamiltonian line graphs of hypergraphs

Issue Information

Strong chromatic index and Hadwiger number

Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes

Asymptotically good edge correspondence colourings

Radius, girth and minimum degree

Recognizing interval bigraphs by forbidden patterns

Filter options

Publication date

Keywords

INFONA - science communication portal

Journal of Graph Theory

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options