About: Spectrally degenerate graphs: Hereditary case

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Spectrally degenerate graphs: Hereditary case Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1016/j.jctb.2012.05.002
Description	It is well known that the spectral radius of a tree whose maximum degree is Delta cannot exceed 2 root Delta - 1. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed root 8 Delta + 10, and more generally, for all d-degenerate graphs, where the corresponding upper bound is root 4d Delta. Following this, we say that a graph G is spectrally d-degenerate if every subgraph H of G has spectral radius at most root d Delta(H). In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally d-degenerate graph G contains a vertex whose degree is at most 4d log(2)(Delta(G)/d) (if Delta(G) }= 2d). It is shown that the dependence on Delta in this upper bound cannot be eliminated, as long as the dependence on d is subexponential. It is also proved that the problem of deciding if a graph is spectrally d-degenerate is Co-NP-complete. (C) 2012 Elsevier Inc. All rights reserved. It is well known that the spectral radius of a tree whose maximum degree is Delta cannot exceed 2 root Delta - 1. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed root 8 Delta + 10, and more generally, for all d-degenerate graphs, where the corresponding upper bound is root 4d Delta. Following this, we say that a graph G is spectrally d-degenerate if every subgraph H of G has spectral radius at most root d Delta(H). In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally d-degenerate graph G contains a vertex whose degree is at most 4d log(2)(Delta(G)/d) (if Delta(G) }= 2d). It is shown that the dependence on Delta in this upper bound cannot be eliminated, as long as the dependence on d is subexponential. It is also proved that the problem of deciding if a graph is spectrally d-degenerate is Co-NP-complete. (C) 2012 Elsevier Inc. All rights reserved. (en)
Title	Spectrally degenerate graphs: Hereditary case Spectrally degenerate graphs: Hereditary case (en)
skos:prefLabel	Spectrally degenerate graphs: Hereditary case Spectrally degenerate graphs: Hereditary case (en)
skos:notation	RIV/00216208:11320/12:10125704!RIV13-GA0-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0545), P(GA201/09/0197)
http://linked.open...iv/cisloPeriodika	5
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Dvořák, Zdeněk
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	170363
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/12:10125704
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Graph, Spectral radius, Degeneracy; RADIUS (en)
http://linked.open.../riv/klicoveSlovo	Graph Degeneracy RADIUS Spectral radius
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[456F84F1AC24]
http://linked.open...i/riv/nazevZdroje	Journal of Combinatorial Theory. Series B
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Graph colorings and flows: structure and applications
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	102
http://linked.open...iv/tvurceVysledku	Dvořák, Zdeněk Mohar, Bojan
http://linked.open...ain/vavai/riv/wos	000308258000004
issn	0095-8956
number of pages	11 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.jctb.2012.05.002
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Spectrally degenerate graphs: Hereditary case

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software