The H-linked degree-sum parameter for special graph families

East Kenney, Lydia; Powell, Jeffrey

doi:10.2140/involve.2017.10.707

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

The $H$-linked degree-sum parameter for special graph families

Lydia East Kenney and Jeffrey Scott Powell

Vol. 10 (2017), No. 4, 707–720

DOI: 10.2140/involve.2017.10.707

Abstract

For a fixed graph $H$ , a graph $G$ is $H$ -linked if any injection $f : V (H) \to V (G)$ can be extended to an $H$ -subdivision in $G$ . The concept of $H$ -linked generalizes several well-known graph theory concepts such as $k$ -connected, $k$ -linked, and $k$ -ordered. In 2012, Ferrara et al. proved a sharp $σ_{2}$ (or degree-sum) bound for a graph to be $H$ -linked. In particular, they proved that any graph $G$ with $n > 20 | E (H) |$ vertices and $σ_{2} (G) \geq n + a (H) - 2$ is $H$ -linked, where $a (H)$ is a parameter maximized over certain partitions of $V (H)$ . However, they do not discuss the calculation of $a (H)$ in their work. In this paper, we prove the exact value of $a (H)$ in the cases when $H$ is a path, a cycle, a union of stars, a complete graph, and a complete bipartite graph. Several of these results lead to new degree-sum conditions for particular graph classes while others provide alternate proofs of previously known degree-sum conditions.

PDF Access Denied

However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/involve

We have not been able to recognize your IP address 3.238.125.76 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

Keywords

H-linked, path, cycle, degree-sum, Ore condition

Mathematical Subject Classification 2010

Primary: 05C35, 05C38

Secondary: 05C83

Milestones

Received: 5 May 2016

Revised: 1 July 2016

Accepted: 11 July 2016

Published: 7 March 2017

Communicated by Jerrold Griggs

Authors

Lydia East Kenney
Smiths Station High School 4228 Lee Rd. 430 Smiths Station, AL 36877 United States

Jeffrey Scott Powell
Department of Mathematics and Computer Science Samford University 800 Lakeshore Drive Birmingham, AL 35229 United States

Vol. 10, No. 4, 2017