Gotowe bibliografie tematyczne / 2-connected outerplanar graphs / Artykuły w czasopismach

Artykuły w czasopismach na temat „2-connected outerplanar graphs”

Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: 2-connected outerplanar graphs.

Autor: Grafiati

Data publikacji: 25 maja 2024

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Sprawdź 17 najlepszych artykułów w czasopismach naukowych na temat „2-connected outerplanar graphs”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

DRMOTA, MICHAEL, OMER GIMÉNEZ i MARC NOY. "The Maximum Degree of Series-Parallel Graphs". Combinatorics, Probability and Computing 20, nr 4 (31.05.2011): 529–70. http://dx.doi.org/10.1017/s0963548311000198.

Pełny tekst źródła

Streszczenie:

We prove that the maximum degree Δn of a random series-parallel graph with n vertices satisfies Δn/logn → c in probability, and Δn ~ c logn for a computable constant c > 0. The same kind of result holds for 2-connected series-parallel graphs, for outerplanar graphs, and for 2-connected outerplanar graphs.

Style APA, Harvard, Vancouver, ISO itp.

Velona, Vasiliki. "Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs". Discrete Mathematics 341, nr 12 (grudzień 2018): 3402–14. http://dx.doi.org/10.1016/j.disc.2018.08.027.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Tang, Yunfeng, Huixin Yin i Miaomiao Han. "Star edge coloring of $ K_{2, t} $-free planar graphs". AIMS Mathematics 8, nr 6 (2023): 13154–61. http://dx.doi.org/10.3934/math.2023664.

Pełny tekst źródła

Streszczenie:

<abstract><p>The star chromatic index of a graph $ G $, denoted by $ \chi{'}_{st}(G) $, is the smallest number of colors required to properly color $ E(G) $ such that every connected bicolored subgraph is a path with no more than three edges. A graph is $ K_{2, t} $-free if it contains no $ K_{2, t} $ as a subgraph. This paper proves that every $ K_{2, t} $-free planar graph $ G $ satisfies $ \chi_{st}'(G)\le 1.5\Delta +20t+20 $, which is sharp up to the constant term. In particular, our result provides a common generalization of previous results on star edge coloring of outerplanar graphs by Bezegová et al.(2016) and of $ C_4 $-free planar graphs by Wang et al.(2018), as those graphs are subclasses of $ K_{2, 3} $-free planar graphs.</p></abstract>

Style APA, Harvard, Vancouver, ISO itp.

Brezovnik, Simon, Niko Tratnik i Petra Žigert Pleteršek. "Resonance Graphs and a Binary Coding of Perfect Matchings of Outerplane Bipartite Graphs". Match Communications in Mathematical and in Computer Chemistry 90, nr 2 (kwiecień 2023): 453–68. http://dx.doi.org/10.46793/match.90-2.453b.

Pełny tekst źródła

Streszczenie:

The aim of this paper is to investigate resonance graphs of 2- connected outerplane bipartite graphs, which include various families of molecular graphs. Firstly, we present an algorithm for a binary coding of perfect matchings of these graphs. Further, 2- connected outerplane bipartite graphs with isomorphic resonance graphs are considered. In particular, it is shown that if two 2- connected outerplane bipartite graphs are evenly homeomorphic, then its resonance graphs are isomorphic. Moreover, we prove that for any 2-connected outerplane bipartite graph G there exists a catacondensed even ring systems H such that the resonance graphs of G and H are isomorphic. We conclude with the characterization of 2-connected outerplane bipartite graphs whose resonance graphs are daisy cubes.

Style APA, Harvard, Vancouver, ISO itp.

Leydold, Josef, i Peter F. Stadler. "Minimal Cycle Bases of Outerplanar Graphs". Electronic Journal of Combinatorics 5, nr 1 (27.02.1998). http://dx.doi.org/10.37236/1354.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Chan, Tsz Lung. "Contractible Edges in 2-Connected Locally Finite Graphs". Electronic Journal of Combinatorics 22, nr 2 (15.06.2015). http://dx.doi.org/10.37236/4414.

Pełny tekst źródła

Streszczenie:

In this paper, we prove that every contraction-critical 2-connected infinite graph has no vertex of finite degree and contains uncountably many ends. Then, by investigating the distribution of contractible edges in a 2-connected locally finite infinite graph $G$, we show that the closure of the subgraph induced by all the contractible edges in the Freudenthal compactification of $G$ is 2-arc-connected. Finally, we characterize all 2-connected locally finite outerplanar graphs nonisomorphic to $K_3$ as precisely those graphs such that every vertex is incident to exactly two contractible edges as well as those graphs such that every finite bond contains exactly two contractible edges.

Style APA, Harvard, Vancouver, ISO itp.

Kraus, Veronika. "The degree distribution in unlabelled $2$-connected graph families". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AM,..., Proceedings (1.01.2010). http://dx.doi.org/10.46298/dmtcs.2773.

Pełny tekst źródła

Streszczenie:

International audience We study the random variable $X_n^k$, counting the number of vertices of degree $k$ in a randomly chosen $2$-connected graph of given families. We prove a central limit theorem for $X_n^k$ with expected value $\mathbb{E}X_n^k \sim \mu_kn$ and variance $\mathbb{V}X_n^k \sim \sigma_k^2n$, both asymptotically linear in $n$, for both rooted and unrooted unlabelled $2$-connected outerplanar or series-parallel graphs.

Style APA, Harvard, Vancouver, ISO itp.

Feng, Xinge, Xingchao Deng i Junqing Cai. "Anti-van der Waerden Numbers of Some 2-Connected Outerplanar Graphs". Journal of Interconnection Networks, 6.04.2024. http://dx.doi.org/10.1142/s0219265924500051.

Pełny tekst źródła

Streszczenie:

Given a graph [Formula: see text] and a positive integer [Formula: see text], the anti-van der Waerden number [Formula: see text] is defined as the minimum positive integer [Formula: see text] such that every exact [Formula: see text]-coloring of the vertices of [Formula: see text] admits a rainbow [Formula: see text]-AP. In this paper, we determine the exact value of [Formula: see text] if [Formula: see text] is a [Formula: see text]-connected outerplanar graph with diameters [Formula: see text].

Style APA, Harvard, Vancouver, ISO itp.

Liu, Qi, i Douglas B. West. "Tree-Thickness and Caterpillar-Thickness under Girth Constraints". Electronic Journal of Combinatorics 15, nr 1 (21.07.2008). http://dx.doi.org/10.37236/817.

Pełny tekst źródła

Streszczenie:

We study extremal problems for decomposing a connected $n$-vertex graph $G$ into trees or into caterpillars. The least size of such a decomposition is the tree thickness $\theta_{\bf T}(G)$ or caterpillar thickness $\theta_{\bf C}(G)$. If $G$ has girth $g$ with $g\ge 5$, then $\theta_{\bf T}(G)\le \lfloor{n/g}\rfloor+1$. We conjecture that the bound holds also for $g=4$ and prove it when $G$ contains no subdivision of $K_{2,3}$ with girth 4. For $\theta_{\bf C}$, we prove that $\theta_{\bf C}(G)\le\lceil{(n-2)/4}\rceil$ when $G$ has girth at least $6$ and is not a $6$-cycle. For triangle-free graphs, we conjecture that $\theta_{\bf C}(G)\le\lceil{3n/8}\rceil$ and prove it for outerplanar graphs. For $2$-connected graphs with girth $g$, we conjecture that $\theta_{\bf C}(G)\le \lfloor{n/g}\rfloor$ when $n\ge\max\{6,g^2/2\}$ and prove it for outerplanar graphs. All the bounds are sharp (sharpness in the $\lceil{3n/8}\rceil$ bound is shown only for $n\equiv 5$ mod $8$).

Style APA, Harvard, Vancouver, ISO itp.

Davis, Robert, i Tianran Chen. "Computing Volumes of Adjacency Polytopes via Draconian Sequences". Electronic Journal of Combinatorics 29, nr 1 (25.03.2022). http://dx.doi.org/10.37236/9768.

Pełny tekst źródła

Streszczenie:

Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The ``"PQ-type" adjacency polytope, denoted $\nabla^{\mathrm{PQ}}_G$ and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for $\nabla^{\mathrm{PQ}}_G$ can be rephrased as counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $1$ and, for $2$-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $\nabla^{\mathrm{PQ}}_G$ when $G$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs $G$ which are planar but not outerplanar that are worth additional study.

Style APA, Harvard, Vancouver, ISO itp.

Bachstein, Anna, i Wayne Goddard. "The Lower Bipartite Number of a Graph". Mathematica Pannonica, 7.02.2023. http://dx.doi.org/10.1556/314.2023.00003.

Pełny tekst źródła

Streszczenie:

For a graph G, we define the lower bipartite number LB(G) as the minimum order of a maximal induced bipartite subgraph of G. We study the parameter, and the related parameter bipartite domination, providing bounds both in general graphs and in some graph families. For example, we show that there are arbitrarily large 4-connected planar graphs G with LB(G) = 4 but a 5-connected planar graph has linear LB(G). We also show that if G is a maximal outerplanar graph of order n, then LB(G) lies between (n + 2)/3 and 2 n/3, and these bounds are sharp.

Style APA, Harvard, Vancouver, ISO itp.

Carmesin, Johannes, i Tsvetomir Mihaylov. "Outerspatial 2-Complexes: Extending the Class of Outerplanar Graphs to Three Dimensions". Electronic Journal of Combinatorics 30, nr 3 (11.08.2023). http://dx.doi.org/10.37236/10539.

Pełny tekst źródła

Streszczenie:

We introduce the class of outerspatial 2-complexes as the natural generalisation of the class of outerplanar graphs to three dimensions. Answering a question of O-joung Kwon, we prove that a locally 2-connected 2-complex is outerspatial if and only if it does not contain a surface of positive genus as a subcomplex and does not have a space minor that is a generalised cone over $K_4$ or $K_{2,3}$. This is applied to nested plane embeddings of graphs; that is, plane embeddings constrained by conditions placed on a set of cycles of the graph.

Style APA, Harvard, Vancouver, ISO itp.

Stufler, Benedikt. "Asymptotic Properties of Random Unlabelled Block-Weighted Graphs". Electronic Journal of Combinatorics 28, nr 4 (19.11.2021). http://dx.doi.org/10.37236/9923.

Pełny tekst źródła

Streszczenie:

We study the asymptotic shape of random unlabelled graphs subject to certain subcriticality conditions. The graphs are sampled with probability proportional to a product of Boltzmann weights assigned to their $2$-connected components. As their number of vertices tends to infinity, we show that they admit the Brownian tree as Gromov–Hausdorff–Prokhorov scaling limit, and converge in a strengthened Benjamini–Schramm sense toward an infinite random graph. We also consider models of random graphs that are allowed to be disconnected. Here a giant connected component emerges and the small fragments converge without any rescaling towards a finite random limit graph. Our main application of these general results treats subcritical classes of unlabelled graphs. We study the special case of unlabelled outerplanar graphs in depth and calculate its scaling constant.

Style APA, Harvard, Vancouver, ISO itp.

Soto, Mauricio, i Christopher Thraves-Caro. "p-box: a new graph model". Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 1, Graph Theory (27.03.2015). http://dx.doi.org/10.46298/dmtcs.2121.

Pełny tekst źródła

Streszczenie:

Graph Theory International audience In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.

Style APA, Harvard, Vancouver, ISO itp.

Dębski, Michał, Piotr Micek, Felix Schröder i Stefan Felsner. "Improved Bounds for Centered Colorings". Advances in Combinatorics, 16.08.2021. http://dx.doi.org/10.19086/aic.27351.

Pełny tekst źródła

Streszczenie:

A vertex coloring $\phi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$ either $\phi$ uses more than $p$ colors on $H$ or there is a color that appears exactly once on $H$. Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function $f$ such that for every $p\geq1$, every graph in the class admits a $p$-centered coloring using at most $f(p)$ colors. In this paper, we give upper bounds for the maximum number of colors needed in a $p$-centered coloring of graphs from several widely studied graph classes. We show that: (1) planar graphs admit $p$-centered colorings with $O(p^3\log p)$ colors where the previous bound was $O(p^{19})$; (2) bounded degree graphs admit $p$-centered colorings with $O(p)$ colors while it was conjectured that they may require exponential number of colors. All these upper bounds imply polynomial algorithms for computing the colorings. Prior to this work there were no non-trivial lower bounds known. We show that: (4) there are graphs of treewidth $t$ that require $\binom{p+t}{t}$ colors in any $p$-centered coloring. This bound matches the upper bound; (5) there are planar graphs that require $\Omega(p^2\log p)$ colors in any $p$-centered coloring. We also give asymptotically tight bounds for outerplanar graphs and planar graphs of treewidth $3$. We prove our results with various proof techniques. The upper bound for planar graphs involves an application of a recent structure theorem while the upper bound for bounded degree graphs comes from the entropy compression method. We lift the result for bounded degree graphs to graphs avoiding a fixed topological minor using the Grohe-Marx structure theorem.

Style APA, Harvard, Vancouver, ISO itp.

Raman, Rajiv, i Karamjeet Singh. "On Hypergraph Supports." European Conference on Combinatorics, Graph Theory and Applications, nr 12 (28.08.2023). http://dx.doi.org/10.5817/cz.muni.eurocomb23-107.

Pełny tekst źródła

Streszczenie:

Let $\mathcal{H}=(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ on the elements in $E$ is connected. We consider hypergraphs defined on a host graph. Given a graph $G=(V,E)$, with $c:V\to\{\R,\B\}$ and a collection of connected subgraphs $\mathcal{H}$ of $G$, a primal support is a graph $Q$ on $\B(V)$ such that for each $H\in \mathcal{H}$, the subgraph $Q[\B(H)]$ on vertices $\B(H)=H\cap c^{-1}(\B)$ is connected. A \emph{dual support} is a graph $Q^*$ on $\mathcal{H}$ s.t. for each $v\in X$, the subgraph $Q^*[\mathcal{H}_v]$ is connected, where $\mathcal{H}_v=\{H\in\mathcal{H}: v\in H\}$. We present sufficient conditions on the host graph and hyperedges so that the resulting support comes from a restricted family. We primarily study two classes of graphs: $(1)$ If the host graph has genus $g$ and the hypergraphs satisfy a topological condition of being \emph{cross-free}, then there is a primal and a dual support of genus at most $g$. $(2)$ If the host graph has treewidth $t$ and the hyperedges satisfy a combinatorial condition of being \emph{non-piercing}, then there exist primal and dual supports of treewidth $O(2^t)$. We show that this exponential blow-up is sometimes necessary. As an intermediate case, we also study the case when the host graph is outerplanar. Finally, we show applications of our results to packing and covering, and coloring problems on geometric hypergraphs.

Style APA, Harvard, Vancouver, ISO itp.

Oliveira, Mateus de Oliveira. "On Supergraphs Satisfying CMSO Properties". Logical Methods in Computer Science Volume 17, Issue 4 (29.11.2021). http://dx.doi.org/10.46298/lmcs-17(4:14)2021.

Pełny tekst źródła

Streszczenie:

Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a connected graph $G$ of maximum degree at most $\Delta$, and determines, in time $f(|\varphi|,t)\cdot 2^{O(\Delta \cdot t)}\cdot |G|^{O(t)}$, whether $G$ has a supergraph $G'$ of treewidth at most $t$ such that $G'\models \varphi$. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time $f(d)\cdot 2^{O(\Delta \cdot d)}\cdot |G|^{O(d)}$, whether a connected graph of maximum degree $\Delta$ has a planar supergraph of diameter at most $d$. Additionally, we show that for each fixed $k$, the problem of determining whether $G$ has an $k$-outerplanar supergraph of diameter at most $d$ is strongly uniformly fixed parameter tractable with respect to the parameter $d$. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter $\mathbf{p}$. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!