Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group

100%
Belkhechine H., Ille P., Woodrow R. E.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
175-209
EN
Let V be a finite vertex set and let (𝔸, +) be a finite abelian group. An 𝔸-labeled and reversible 2-structure defined on V is a function g : (V × V) \ {(v, v) : v ∈ V } → 𝔸 such that for distinct u, v ∈ V, g(u, v) = −g(v, u). The set of 𝔸-labeled and reversible 2-structures defined on V is denoted by ℒ(V, 𝔸). Given g ∈ ℒ(V, 𝔸), a subset X of V is a clan of g if for any x, y ∈ X and v ∈ V \ X, g(x, v) = g(y, v). For example, ∅, V and {v} (for v ∈ V) are clans of g, called trivial. An element g of ℒ(V, 𝔸) is primitive if |V | ≥ 3 and all the clans of g are trivial. The set of the functions from V to 𝔸 is denoted by 𝒮(V, 𝔸). Given g ∈ ℒ(V, 𝔸), with each s ∈ 𝒮(V, 𝔸) is associated the switch gs of g by s defined as follows: given distinct x, y ∈ V, gs(x, y) = s(x) + g(x, y) − s(y). The switching class of g is {gs : s ∈ 𝒮(V, 𝔸)}. Given a switching class 𝔖 ⊆ ℒ(V, 𝔸) and X ⊆ V, {g↾(X × X)\{(x,x):x∈X} : g ∈ 𝔖} is a switching class, denoted by 𝔖[X]. Given a switching class 𝔖 ⊆ ℒ(V, 𝔸), a subset X of V is a clan of 𝔖 if X is a clan of some g ∈ 𝔖. For instance, every X ⊆ V such that min(|X|, |V \ X|) ≤ 1 is a clan of 𝔖, called trivial. A switching class 𝔖 ⊆ ℒ(V, 𝔸) is primitive if |V | ≥ 4 and all the clans of 𝔖 are trivial. Given a primitive switching class 𝔖 ⊆ ℒ(V, 𝔸), 𝔖 is critical if for each v ∈ V, 𝔖 − v is not primitive. First, we translate the main results on the primitivity of 𝔸-labeled and reversible 2-structures in terms of switching classes. For instance, we prove the following. For a primitive switching class 𝔖 ⊆ ℒ(V, 𝔸) such that |V | ≥ 8, there exist u, v ∈ V such that u ≠ v and 𝔖[V \ {u, v}] is primitive. Second, we characterize the critical switching classes by using some of the critical digraphs described in [Y. Boudabous and P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839–2846].
2
Content available remote

One-Three Join: A Graph Operation and Its Consequences

81%
Shalu M. A., Devi Yamini S.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
633-647
EN
In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for ℳH.
3
Content available remote

Structural Properties of Recursively Partitionable Graphs with Connectivity 2

81%
Baudon O., Bensmail J., Foucaud F., Pilśniak M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
89-115
EN
A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must not only be connected but also fulfil additional conditions. In this paper, we point out some structural properties of OL-AP and R-AP graphs with connectivity 2. In particular, we show that deleting a cut pair of these graphs results in a graph with a bounded number of components, some of whom have a small number of vertices. We obtain these results by studying a simple class of 2-connected graphs called balloons.
4
Content available remote

The Graphs Whose Permanental Polynomials Are Symmetric

81%
Li W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
233-243
EN
The permanental polynomial [...] π(G,x)=∑i=0nbixn−i $\pi (G,x) = \sum\nolimits_{i = 0}^n {b_i x^{n - i} }$ of a graph G is symmetric if bi = bn−i for each i. In this paper, we characterize the graphs with symmetric permanental polynomials. Firstly, we introduce the rooted product H(K) of a graph H by a graph K, and provide a way to compute the permanental polynomial of the rooted product H(K). Then we give a sufficient and necessary condition for the symmetric polynomial, and we prove that the permanental polynomial of a graph G is symmetric if and only if G is the rooted product of a graph by a path of length one.
5
Content available remote

Kaleidoscopic Colorings of Graphs

81%
Chartrand G., English S., Zhang P.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
711-727
EN
For an r-regular graph G, let c : E(G) → [k] = {1, 2, . . . , k}, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular graph G is called a k-kaleidoscope if G has a k-kaleidoscopic coloring. It is shown that for each integer k ≥ 3, the complete graph Kk+3 is a k-kaleidoscope and the complete graph Kn is a 3-kaleidoscope for each integer n ≥ 6. The largest order of an r-regular 3-kaleidoscope is [...] (r−12) $\left( {\matrix{{r - 1} \cr 2 } } \right)$ . It is shown that for each integer r ≥ 5 such that r ≢ 3 (mod 4), there exists an r-regular 3-kaleidoscope of order [...] (r−12) $\left( {{{r - 1} \over 2}} \right)$ .
6
Content available remote

Characterizing Atoms that Result from Decomposition by Clique Separators

62%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
587-594
EN
A graph is defined to be an atom if no minimal vertex separator induces a complete subgraph; thus, atoms are the graphs that are immune to clique separator decomposition. Atoms are characterized here in two ways: first using generalized vertex elimination schemes, and then as generalizations of 2-connected unichord-free graphs (the graphs in which every minimal vertex separator induces an edgeless subgraph).
7
Content available remote

Requiring that Minimal Separators Induce Complete Multipartite Subgraphs

62%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
263-273
EN
Complete multipartite graphs range from complete graphs (with every partite set a singleton) to edgeless graphs (with a unique partite set). Requiring minimal separators to all induce one or the other of these extremes characterizes, respectively, the classical chordal graphs and the emergent unichord-free graphs. New theorems characterize several subclasses of the graphs whose minimal separators induce complete multipartite subgraphs, in particular the graphs that are 2-clique sums of complete, cycle, wheel, and octahedron graphs.
8
Content available remote

Split Euler Tours In 4-Regular Planar Graphs

62%
Couch P., Daniel B. D., Guidry R., Paul Wright W.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
23-30
EN
The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.
9
Content available remote

The hyperbolicity constant of infinite circulant graphs

62%
Rodríguez J. M., Sigarreta J. M.
Open Mathematics
|
2017
|
tom 15
|
nr 1
800-814
EN
If X is a geodesic metric space and x1, x2, x3 ∈ X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. Deciding whether or not a graph is hyperbolic is usually very difficult; therefore, it is interesting to find classes of graphs which are hyperbolic. A graph is circulant if it has a cyclic group of automorphisms that includes an automorphism taking any vertex to any other vertex. In this paper we prove that infinite circulant graphs and their complements are hyperbolic. Furthermore, we obtain several sharp inequalities for the hyperbolicity constant of a large class of infinite circulant graphs and the precise value of the hyperbolicity constant of many circulant graphs. Besides, we give sharp bounds for the hyperbolicity constant of the complement of every infinite circulant graph.
10
Content available remote

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

52%
Metelsky Y., Schemeleva K., Werner F.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
13-28
EN
We characterize the class [...] L32 $L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 $L_3^2 $ in the class of threshold graphs, where n is the number of vertices of a tested graph.
11
Content available remote

Non-hyperbolicity in random regular graphs and their traffic characteristics

52%
Tucci G.
Open Mathematics
|
2013
|
tom 11
|
nr 9
1593-1597
EN
In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.
12
Content available remote

Gromov hyperbolicity of planar graphs

52%
Cantón A., Granados A., Pestana D., Rodríguez J.
Open Mathematics
|
2013
|
tom 11
|
nr 10
1817-1830
EN
We prove that under appropriate assumptions adding or removing an infinite amount of edges to a given planar graph preserves its non-hyperbolicity, a result which is shown to be false in general. In particular, we make a conjecture that every tessellation graph of ℝ2 with convex tiles is non-hyperbolic; it is shown that in order to prove this conjecture it suffices to consider tessellation graphs of ℝ2 such that every tile is a triangle and a partial answer to this question is given. A weaker version of this conjecture stating that every tessellation graph of ℝ2 with rectangular tiles is non-hyperbolic is given and partially answered. If this conjecture were true, many tessellation graphs of ℝ2 with tiles which are parallelograms would be non-hyperbolic.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.