Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- K-forcing number (2)
- Block (1)
- Claw-free graph (1)
- Connected hypergraph (1)
- Connectivity (1)
-
- Cut edge (1)
- Cut vertex (1)
- Cycle (1)
- Euclidean distance graph (1)
- Fractional chromatic number (1)
- Girth (1)
- Graph isomorphisms (1)
- Graph theory (1)
- Hypergraph (1)
- Incidence graph (1)
- Independent set (1)
- K-forcing set (1)
- Nullity (1)
- Path (1)
- Path-tables (1)
- Proper coloring (1)
- Proper connection number (1)
- Second Hamiltonian cycle (1)
- Separating vertex (1)
- Sheehan’s conjecture (1)
- Trail (1)
- Trees (1)
- Triangle-free graphs (1)
- Vertex independence number (1)
- Walk (1)
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak
Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak
Theory and Applications of Graphs
The (vertex) path-table of a tree Τ contains quantitative information about the paths in Τ. The entry (i,j) of this table gives the number of paths of length j passing through vertex vi. The path-table is a slight variation of the notion of path layer matrix. In this survey we review some work done on the vertex path-table of a tree and also introduce the edge path-table. We show that in general, any type of path-table of a tree Τ does not determine Τ uniquely. We shall show that in trees, the number of paths passing through …
Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter
Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter
Theory and Applications of Graphs
The zero-forcing number, Ζ(G) is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the graph. A simple lower bound is δ ≤ Ζ(G) where δ is the minimum degree. An improvement of this bound is provided in the case that G has girth of at least 5. In particular, it is shown that 2δ − 2 ≤ Ζ(G) for graphs with girth of at least 5; this can be further improved when G has a small cut set. Lastly, a conjecture is made regarding a lower bound for Ζ(G) as a …
An Isomorphism Problem In Z2, Matt Noble
An Isomorphism Problem In Z2, Matt Noble
Theory and Applications of Graphs
We consider Euclidean distance graphs with vertex set ℚ2 or ℤ2 and address the possibility or impossibility of finding isomorphisms between such graphs. It is observed that for any distances d1, d2 the non-trivial distance graphs G(ℚ2, d1) and G(ℚ2, d2) are isomorphic. Ultimately it is shown that for distinct primes p1, p2 the non-trivial distance graphs G(ℤ2, √p1) and G(ℤ2, √p2) are not isomorphic. We conclude with a few additional questions related to this work.
Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi
Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi
Theory and Applications of Graphs
Sheehan conjectured in 1975 that every Hamiltonian regular simple graph of even degree at least four contains a second Hamiltonian cycle. We prove that most claw-free Hamiltonian graphs with minimum degree at least 3 have a second Hamiltonian cycle and describe the structure of those graphs not covered by our result. By this result, we show that Sheehan’s conjecture holds for claw-free graphs whose order is not divisible by 6. In addition, we believe that the structure that we introduce can be useful for further studies on claw-free graphs.
Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna
Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna
Theory and Applications of Graphs
In this paper we study various fundamental connectivity properties of hypergraphs from a graph-theoretic perspective, with the emphasis on cut edges, cut vertices, and blocks. We prove a number of new results involving these concepts. In particular, we describe the exact relationship between the block decomposition of a hypergraph and the block decomposition of its incidence graph.
Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant
Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant
Theory and Applications of Graphs
A path in an edge-colored graph is properly colored if no two consecutive edges receive the same color. In this survey, we gather results concerning notions of graph connectivity involving properly colored paths.
Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper
Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper
Theory and Applications of Graphs
The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].
Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha
Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha
Theory and Applications of Graphs
The chromatic number has a well-known interpretation in the area of scheduling. If the vertices of a finite, simple graph are committees, and adjacency of two committees indicates that they must never be in session simultaneously, then the chromatic number of the graph is the smallest number of hours during which the committees/vertices of the graph may all have properly scheduled meetings of one continuous hour each. Slivnik [3] showed that the fractional chromatic number can be similarly characterized. In that characterization, the meetings are allowed to be broken into a finite number of disjoint intervals. Here we consider chromatic …