Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Alpha-labelings (1)
- Alternating Group Graph (1)
- Berge triangle (1)
- Co-NP (1)
- Colored hypergraphs (1)
-
- Conditional Strong Matching Preclusion (1)
- Diameter (1)
- Forcibly biconnected (1)
- Fractional perfect matching; Fractional matching preclusion; Fractional strong matching preclusion; Multiply twisted cube; Locally twisted cube (1)
- Generalized Petersen graph (1)
- Graphical degree sequence (1)
- Graphical partition (1)
- Interconnection Networks (1)
- K-forcing (1)
- Laplacian eigenvalues (1)
- Local search (1)
- Matching; Fractional matching preclusion; Fractional strong matching preclusion; Butterfly network; Augmented butterfly network; Enhanced butterfly network (1)
- Maximum oriented forcing (1)
- NNI (1)
- NP-hard (1)
- Perfect matching (1)
- Petersen graph (1)
- Phylogenetic network (1)
- Ramsey number (1)
- Rearrangement (1)
- SPR (1)
- Signed graph (1)
- Singular subgraph (1)
- Sun graph (1)
- TBR (1)
Articles 1 - 11 of 11
Full-Text Articles in Entire DC Network
Rearrangement Operations On Unrooted Phylogenetic Networks, Remie Janssen, Jonathan Klawitter
Rearrangement Operations On Unrooted Phylogenetic Networks, Remie Janssen, Jonathan Klawitter
Theory and Applications of Graphs
Rearrangement operations transform a phylogenetic tree into another one and hence induce a metric on the space of phylogenetic trees. Popular operations for unrooted phylogenetic trees are NNI (nearest neighbour interchange), SPR (subtree prune and regraft), and TBR (tree bisection and reconnection). Recently, these operations have been extended to unrooted phylogenetic networks, which are generalisations of phylogenetic trees that can model reticulated evolutionary relationships. Here, we study global and local properties of spaces of phylogenetic networks under these three operations. In particular, we prove connectedness and asymptotic bounds on the diameters of spaces of different classes of phylogenetic networks, including …
Conditional Strong Matching Preclusion Of The Alternating Group Graph, Mohamad Abdallah, Eddie Cheng
Conditional Strong Matching Preclusion Of The Alternating Group Graph, Mohamad Abdallah, Eddie Cheng
Theory and Applications of Graphs
The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. Park and Ihm introduced the problem of strong matching preclusion under the condition that no isolated vertex is created as a result of faults. In this paper, we find the conditional strong matching preclusion number for the n-dimensional alternating group graph AGn.
Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang
Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang
Theory and Applications of Graphs
We present an algorithm to test whether a given graphical degree sequence is forcibly biconnected. The worst case time complexity of the algorithm is shown to be exponential but it is still much better than the previous basic algorithm for this problem. We show through experimental evaluations that the algorithm is efficient on average. We also adapt the classic algorithm of Ruskey et al. and that of Barnes and Savage to obtain some enumerative results about forcibly biconnected graphical degree sequences of given length n and forcibly biconnected graphical partitions of given even integer n. Based on these enumerative …
Laplacian Spectral Characterization Of Signed Sun Graphs, Fatemeh Motialah, Mohammad Hassan Shirdareh Haghighi
Laplacian Spectral Characterization Of Signed Sun Graphs, Fatemeh Motialah, Mohammad Hassan Shirdareh Haghighi
Theory and Applications of Graphs
A sun SGn is a graph of order 2n consisting of a cycle Cn, n ≥ 3, to each vertex of it a pendant edge is attached. In this paper, we prove that unbalanced signed sun graphs are determined by their Laplacian spectra. Also we show that a balanced signed sun graph is determined by its Laplacian spectrum if and only if n is odd.
Fractional Strong Matching Preclusion For Two Variants Of Hypercubes, Huifen Ge, Tianlong Ma, Miaolin Wu, Yuzhi Xiao
Fractional Strong Matching Preclusion For Two Variants Of Hypercubes, Huifen Ge, Tianlong Ma, Miaolin Wu, Yuzhi Xiao
Theory and Applications of Graphs
Let F be a subset of edges and vertices of a graph G. If G-F has no fractional perfect matching, then F is a fractional strong matching preclusion set of G. The fractional strong matching preclusion number is the cardinality of a minimum fractional strong matching preclusion set. In this paper, we mainly study the fractional strong matching preclusion problem for two variants of hypercubes, the multiply twisted cube and the locally twisted cube, which are two of the most popular interconnection networks. In addition, we classify all the optimal fractional strong matching preclusion set of each.
Colored Complete Hypergraphs Containing No Rainbow Berge Triangles, Colton Magnant
Colored Complete Hypergraphs Containing No Rainbow Berge Triangles, Colton Magnant
Theory and Applications of Graphs
The study of graph Ramsey numbers within restricted colorings, in particular forbidding a rainbow triangle, has recently been blossoming under the name Gallai-Ramsey numbers. In this work, we extend the main structural tool from rainbow triangle free colorings of complete graphs to rainbow Berge triangle free colorings of hypergraphs. In doing so, some other concepts and results are also translated from graphs to hypergraphs.
Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper
Maximum Oriented Forcing Number For Complete Graphs, Yair Caro, Ryan Pepper
Theory and Applications of Graphs
The maximum oriented k-forcing number of a simple graph G, written MOFk(G), is the maximum directed k-forcing number among all orientations of G. This invariant was recently introduced by Caro, Davila and Pepper in [6], and in the current paper we study the special case where G is the complete graph with order n, denoted Kn . While MOFk(G) is an invariant for the underlying simple graph G, MOFk(Kn) can also be interpreted as an interesting property for tournaments. Our main results …
Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian
Matching Preclusion Of The Generalized Petersen Graph, Ajay Arora, Eddie Cheng, Christopher Melekian
Theory and Applications of Graphs
The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph with no perfect matchings. In this paper we determine the matching preclusion number for the generalized Petersen graph P(n,k) and classify the optimal sets.
Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion
Series-Parallel Operations With Alpha-Graphs, Christian Barrientos, Sarah Minion
Theory and Applications of Graphs
Among difference vertex labelings of graphs, α-labelings are the most restrictive one. A graph is an α-graph if it admits an α-labeling. In this work, we study a new alternative to construct α-graphs using, the well-known, series-parallel operations on smaller α-graphs. As an application of the series operation, we show that all members of a subfamily of all trees with maximum degree 4, obtained using vertex amalgamation of copies of the path Ρ11}, are α-graphs. We also show that the one-point union of up to four copies of Κn,n is an …
Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang
Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang
Theory and Applications of Graphs
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu [18] recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G, denoted by fmp(G), is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G, denoted by fsmp(G), is the minimum number of vertices and edges whose deletion …
Singular Ramsey And Turán Numbers, Yair Caro, Zsolt Tuza
Singular Ramsey And Turán Numbers, Yair Caro, Zsolt Tuza
Theory and Applications of Graphs
We say that a subgraph F of a graph G is singular if the degrees dG(v) are all equal or all distinct for the vertices v ∈ V (F). The singular Ramsey number Rs(F) is the smallest positive integer n such that, for every m at least n, in every edge 2-coloring of Km, at least one of the color classes contains F as a singular subgraph. In a similar flavor, the singular Turán number Ts(n,F) is defined as the maximum number of edges in a graph of order n, …